КК
😍
я понял как работает код. С i[0] i[1] интересный ход
но я не понял сути перемножения
но я не понял сути перемножения
[5] * 5 == [5, 5, 5, 5, 5]
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()вот такая вот ультра-сортировка подсчётом
а почему отбор идет от 0 до 5? Значений может быть куда больше. Или это просто демонстационаая версия
КК
😍
а почему отбор идет от 0 до 5? Значений может быть куда больше. Или это просто демонстационаая версия
ну потому что мне так захотелось, никто не мешает поменять на любой диапозон. но такая сортировка явно выигрывает только в том случае, если диапозон значений не превышает n log n
КК
то есть если в массиве скажем 1000 элементов а диапозон значений 1000000, то такая сортировка по всем фронтам проиграет даже обычной банальной сортировке пузырьком
m
что на вот этой картинке и в книжке наглядно показано
m
что асимптотическая сложность это конечно хорошо, но она показывает как вычислительные затраты будут меняться, а не сами вычислительные затраты
😍
Переслано от Кирилл Картвелишвили
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()вот такая вот ультра-сортировка подсчётом
И еще вопрос зачем эти рандомные числа в lst прибавлять +1? или чтотон прибавляет. Допустим в списке lst есть значения ...4,4,4..
аа понял он пишет сколько в ключе(4) четверок = 3
только потом в список new не залетит число 12?
аа понял он пишет сколько в ключе(4) четверок = 3
только потом в список new не залетит число 12?
КК
😍
И еще вопрос зачем эти рандомные числа в lst прибавлять +1? или чтотон прибавляет. Допустим в списке lst есть значения ...4,4,4..
аа понял он пишет сколько в ключе(4) четверок = 3
только потом в список new не залетит число 12?
аа понял он пишет сколько в ключе(4) четверок = 3
только потом в список new не залетит число 12?
там i[0] находится в квадратных скобках, поэтому интерпретатор видит не 4 * 3, а [4] * 3
😍
мм ок
очень интересно кстати!:)
очень интересно кстати!:)
КК
возьми этот код, нафиг тесты удали, убавь кол-во элементов до 10 и пройдись по нему отладчиком, прям следи за каждой переменной, что где происходит, все дела. это очень полезно, это лучший метод понять, как работает чужой код
КК
что асимптотическая сложность это конечно хорошо, но она показывает как вычислительные затраты будут меняться, а не сами вычислительные затраты
как ускорение в физике) оно не показывает скорость, а показывает скорость изменения скорости
m
ты смотри повнимательнее-тут обитают некоторые люди которые просто любят чужое время потратить и ниче сами не будут проверять или изучать и вообще им это все не особо надо
вот ты как раз тратишь на одного из них
вот ты как раз тратишь на одного из них
😍
ты смотри повнимательнее-тут обитают некоторые люди которые просто любят чужое время потратить и ниче сами не будут проверять или изучать и вообще им это все не особо надо
вот ты как раз тратишь на одного из них
вот ты как раз тратишь на одного из них
зря ты так говоришь
я все проверяю что он мне говорит
я все проверяю что он мне говорит