ПрограмёрALex_hhaНу конкретно я проверял на обычном ascii тексте, это собственно видно из кода генерации строки
1.
s = ''.join(random.choice(string.ascii_letters[0:25]) for _ in range(10000000))
пропущено...
да, я читал, что списки и словари в питоне оптимизированы по самое немогу :) Как написали на SO - "Dictionaries are one of the more heavily tuned parts of Python, since they underlie so much of the language."
Кстати, а сама операция преобразования строки во множество или список/словарь она не является затратной?
проверил :) нет... не является
Итак, берём 3 файла (str.py, str2.py, empty.py... исходники в той же последовательности):
1.
2.
3.
4.
5.
6.
7.
#!/usr/bin/python2.7
import string
str1 = 'a'*100000000
k = set()
for c in str1:
k.add(c)
1.
2.
3.
4.
5.
6.
#!/usr/bin/python2.7
import string
str1 = 'a'*100000000
k = set()
k = set(str1)
1.
2.
3.
4.
#!/usr/bin/python2.7
import string
str1 = 'a'*100000000
моя консоль$ time ./str.py
real 0m6.835s
user 0m6.812s
sys 0m0.032s
$ time ./str2.py
real 0m0.975s
user 0m0.940s
sys 0m0.036s
$ time ./empty.py
real 0m0.113s
user 0m0.024s
sys 0m0.088s
Итак, имеем следующие данные:
1. Строка в 100 000 000 символов создаётся в течении 0.024s . Что логично, учитывая что запись в ячейку памяти это 1 или 2 такта (не вспомню уже), то процессор может за секунду заполнить 6 гигабайт памяти (мы же заполняем значительно меньший объём, всего 100 Мб)
2. Строка в 100 000 000 символов переводится во множество в течении где-то 0.940s. По сути то же чтение и заполнение ячеек памяти, только + механизм вычисления хэш функции для каждой операции записи
3. А вот перебор строки в цикле ведёт к увеличению затрат ещё на 6 секунд.
Теперь надо определить, эта задержка обусловлена циклом как таковым (расходами на его работу в питоне) или же она вызвана именно работой со строкой.
Берём ещё файл (rng.py):
1.
2.
3.
4.
5.
6.
7.
#!/usr/bin/python2.7
import string
str1 = ['a']*100000000
k = set()
for c in str1:
k.add(c)
и меряем скорость перебора не строки, а списка:
консоль$ time ./rng.py
real 0m7.397s
user 0m7.204s
sys 0m0.200s
Ничего не поменялось... всё те же 7 секунд (плюс-минус). Тут я сам был удивлён, потому что изначальное предположение по поводу строк оказалось ошибочным. Дело не в строке, а в цикле! Для перебора множества ситуация тоже не меняется.
После этого я уже начал экспериментировать и нарвался на ожидаемый, но совсем неочевидный эффект. Смотрим файл rng2.py:
1.
2.
3.
4.
5.
6.
#!/usr/bin/python2.7
import string
str1 = ['a']*100000000
k = set()
k = {c for c in str1}
Результат:
консоль$ time ./rng2.py
real 0m2.744s
user 0m2.572s
sys 0m0.172s
ТАДАААААМ!!! Тернарный оператор for...in даёт нам оптимизацию вдвое (разумеется это так сильно заметно только из-за простоты выполняемых операций). Исходя из последнего опыта можно предположить, что очень много времени терялось на создании отдельного объекта строки "с" для каждой конкретной итерации. И при использовании тернарной операции похоже этого не происходит и каждое следующее значение передаётся напрямую в функцию добавления значения во множество. То есть вместо создания объекта строки для переменной "c", а потом ещё его дублирования для записи во множество, теперь происходит создание только одного экземпляра объекта, что изрядно экономит время :)
P.S. Как помним, в питоне всё является объектами. Потому для ускорения работы очень больших циклов, похоже, следует использовать тернарные операции for...in по возможности. Проверял на практике, с числами та же хрень например.
========
больше похоже на подгон под ответ.
1)не важно сколько тактов занимает действие на микропроцессоре, шина обмена с памятью в раз 20 медленее, поэтому там что 2 что 5 тактов - побую, шина влюбом случае будет скорость лимитирующим фактором
2)один такт идёт на декодирование команды, адрес в память строится сегмент смещение, это два регистра выставить на микропроцессоре недо, плюс сама отправка - это если отослать байт в адресс.
3)но 2 сдесь бесмсленно - вы пишете на питоне, ядро которого написано на си наврено, влюбом случае не на ассемблере, так что рассуждать в такие дебри безперспективно
4)подозреваю что команда продублировать 100 000 000 раз один символ будет оптимизирована...ведь соверменная память умеет копировать участки без участия микропроцессора.
ну тоесть микропроцессору не обязательно 100 млн раз отправлять байт в память по адресу.
можно выделить память(скорей всего это не один сплошной кусок будет - но тут не важно) и оставить сразу строку сразу на 8 байт(для 64 битнйо системы) и начиная с этого момента, копировать куски оперативки в оперативку..
5)ваши замеры на питоне как что работает безперспективны. условие -любое, это очень заратная операция для микропроцессора. очень затратная, легче 100 сложений сделать чем одно условие (я про код на ассемблере) - по сути, весь ваш код на питоне, наш на пхп и подобных языках медленее кода написаного толково и скомпиленого толковым компилятором на Си обуславливается именно этими условиями - что в том коде вы на прямую работаете с памятью, и любое действие с чтением присвоением - это работа с адресами в память, вто время как на интерпретируемых языках, это всё проходит через таблицу переменных, а там как ни крути условия будут - ну как минимум проверить наличие переменной, подходящесть типа...
поэтому пытаться чтото сравнивать так дотошно на таком языке как питон - безперспективно.
сравнивать можно различные языковые конструкции, делающие одно и тоже, но никак не то что насравнивали вы.
6)
а рассуждения чесно говоря иногда удивляют...фраза - по сути тоже чтение только есчо вычисление хеш функции... тут какбы ситуация такая, что уже болт забить можно на чтение или не чтение...выщитывать хешфункцию - это основная задача
-- и вот тут можете написать сравнительный тест, в милион ячеек в цикле записать числа от 1 до 1000000, тоже только рандомное число(сохранять всегда ввиде текста число) - и тоже, но хеш значение
