😍
ты наверно имеешь в виду хеш-таблицы. это такая структура данных, которая хранит пары ключ-значение. в питоне такая штука называется словарями (dictionary)
да про них
Size: a a a
2020 May 14
КК
как раз вот в чат плюсовиков случайно полетела сортировка подсчётом, где я использовал словари для хранения количества вхождений определённого элемента
КК
Переслано от Кирилл Картвелишвили...
from time import monotonic
from random import randint
def main():
n = 100
prev = 1
for _ in range(6):
lst = [randint(0, 5) for _ in range(n)]
start = monotonic()
lst = count_sort(lst, range(6))
delta = monotonic() - start
print(delta / prev)
prev = delta
n *= 10
def count_sort(lst, r):
counters = dict.fromkeys(r, 0)
for i in lst: counters[i] += 1
new = []
for i in counters.items():
new += [i[0]] * i[1]
return new
if __name__ == '__main__':
main()вот такая вот ультра-сортировка подсчётом
КК
на main не смотри, там тесты, главное здесь функция count_sort
КК
dict.fromkeys - это метод класса словаря, который создаёт словарь с ключами из последовательности, которая ему передана первым аргументом и каждому этому ключу присваивает второй аргумень
😍
сходу ничего не понятно) а разве со списком такие манипуляции можно делать?
КК
ну да. [1, 2] + [3, 4] вернёт [1, 2, 3, 4]
КК
по сути работает так же как конкатенация строк
😍
Переслано от Кирилл Картвелишвили
from time import monotonic
from random import randint
def main():
n = 100
prev = 1
for _ in range(6):
lst = [randint(0, 5) for _ in range(n)]
start = monotonic()
lst = count_sort(lst, range(6))
delta = monotonic() - start
print(delta / prev)
prev = delta
n *= 10
def count_sort(lst, r):
counters = dict.fromkeys(r, 0)
for i in lst: counters[i] += 1
new = []
for i in counters.items():
new += [i[0]] * i[1]
return new
if __name__ == '__main__':
main()вот такая вот ультра-сортировка подсчётом
то есть в тебя в 1 ключ подается 6 значений?
😍
😍
то есть в тебя в 1 ключ подается 6 значений?
ой нет 6 ключей со значен 0
😍
😍
Переслано от Кирилл Картвелишвили
from time import monotonic
from random import randint
def main():
n = 100
prev = 1
for _ in range(6):
lst = [randint(0, 5) for _ in range(n)]
start = monotonic()
lst = count_sort(lst, range(6))
delta = monotonic() - start
print(delta / prev)
prev = delta
n *= 10
def count_sort(lst, r):
counters = dict.fromkeys(r, 0)
for i in lst: counters[i] += 1
new = []
for i in counters.items():
new += [i[0]] * i[1]
return new
if __name__ == '__main__':
main()вот такая вот ультра-сортировка подсчётом
и еще что такое .items()
КК
ну скорее всего там очень много незнакомых тебе синтаксических конструкций. на деле алгоритм очень простой.
на вход поступают два параметра.
первый - сам список, ну например [1, 3, 2, 1, 1, 3, 4, 4, 3, 2, 0, 0, 4, 2]
второй - диапозон допустимых значений (его можно вычислить и внутри самой функции, просто за один проход найти минимальный и максимальный элемент)
далее мы создаём словарь такого вида
counters = {
'0': 0,
'1': 0,
'2': 0,
'3': 0,
'4': 0,
}
это наши счётчики.
далее нам нужно подсчитать сколько раз встречается каждый элемент в списке, просто увеличиваем нужный счётчик при встрече элемента.
осталось только создать новый список и поместить в него нужное количество всех элементов исходного списка.
значит бежим по нашему словарю. метод items возвращает список кортежей вида (ключ, значение). соответственно по i[0] я доступаюсь к ключу, а по i[1] к значению, то есть количеству вхождений.
как-то так
на вход поступают два параметра.
первый - сам список, ну например [1, 3, 2, 1, 1, 3, 4, 4, 3, 2, 0, 0, 4, 2]
второй - диапозон допустимых значений (его можно вычислить и внутри самой функции, просто за один проход найти минимальный и максимальный элемент)
далее мы создаём словарь такого вида
counters = {
'0': 0,
'1': 0,
'2': 0,
'3': 0,
'4': 0,
}
это наши счётчики.
далее нам нужно подсчитать сколько раз встречается каждый элемент в списке, просто увеличиваем нужный счётчик при встрече элемента.
осталось только создать новый список и поместить в него нужное количество всех элементов исходного списка.
значит бежим по нашему словарю. метод items возвращает список кортежей вида (ключ, значение). соответственно по i[0] я доступаюсь к ключу, а по i[1] к значению, то есть количеству вхождений.
как-то так
КК
по сути хеш-таблица отображает что-то, на что-то.
но первое что-то обязательно должно быть константой, это логично
но первое что-то обязательно должно быть константой, это логично
😍
я понял как работает код. С i[0] i[1] интересный ход
но я не понял сути перемножения
но я не понял сути перемножения
😍
по сути хеш-таблица отображает что-то, на что-то.
но первое что-то обязательно должно быть константой, это логично
но первое что-то обязательно должно быть константой, это логично
а в теории можно ключ поменять?