baragoz
Дек. 30, 2010 11:37:50
что такое “охапка”?
Андрей Светлов
Дек. 30, 2010 11:39:21
ИМХО, задачка звучит как “удалить повторяющиеся”, а не “случайно перемешать при этом оставшиеся”.
Андрей Светлов
Дек. 30, 2010 11:41:59
Имелось в виду, что dst.writelines будет работать быстрее нескольких dst.write.
Разница мизерная, только на игре с GIL. Не верите - смотрите исходники.
Файловый кеш практически всё нивелирует.
baragoz
Дек. 30, 2010 11:42:10
Кстати у меня почему-то на такую конструкцию ругается
for line in with open(filename, 'r'):
пришлось вот так переделать:
with open(filename, 'r') as srs:
for line in srs:
...
Андрей Светлов
Дек. 30, 2010 11:43:30
то я ошибся. Должно быть
for line in open(filename, ‘r’):
Ваш вариант даже лучше - файл корректней закрывается
baragoz
Дек. 30, 2010 11:46:56
Аааа ясно.
Спасибо огромное за урок! =)
Качаю книгу Кнута, хочу почитать про его алгоритм с таблицами (интернет подвел на этот раз с описанием).
Если возникнут вопросы буду сюда писать и надеяться на Ваше терпение =) Уж очень хочется посмотреть на его хеш-таблицу, индексы и т.д. наглядно.
doza_and
Дек. 30, 2010 13:27:54
Мне код Андрея тоже понравился, но тема про рациональное использование процессора в котором как указал автор - 4 ядра. Чем больше файл тем больше времени будет проводится в
used.add(line)
if line not in used:
Поэтому возникает вопрос - можно это на многих процессорах пустить? Логично было-бы иметь
used.add() которое внутри раскидывается по процессорам. Есть такая штука?
Андрей Светлов
Дек. 30, 2010 14:40:36
Сомневаюсь. Поток входных данных один, выполнение строго последовательное.
Не вижу простого способа распараллелить на потоки или на процессы.
И, главное, затык был в другом. Алгоритмическая сложность и большой объем.
Немного о кеше:
Полмиллиона строк - это полсотни мегабайт для типичного лога. Объекты строк равномерно размазаны по этим мегабайтам. Сравнение строк быстрое (сперва пробуется все тот же хэш), но эти строки перед использованием нужно переместить в L2 кэш процессора. L1 пренебрежимо быстрый.
L2 бывает разный, но в любом случае это - несколько мегабайт. Целиком не помещается. Процессор постоянно промахивается и получает пенальти, пока данные перегоняются из памяти в L2. И это - основные трудозатраты (вычислений почти нет).
Для хэш-таблицы ее тело - это непрерывный массив пар хэш (int)-> элемент (PyObject*).
Все тело прочно сидит в L2 и промахов нет - вот оно и гораздо быстрее.
asilyator
Янв. 9, 2011 16:47:21
baragoz
# проверка наличия повторяющихся элемнетов
for i in xrange(len(list)-1, -1, -1):
if list.count(list) != 1:
del list
Взять_и_уе..ть.jpg. У тебя проверка будет с классом сложности O(n**2) вместо O(n*log(n)).
Собсно до меня это уже написали.
Вместо set можно взять dict, разницы по скорости ведь не будет?
А пенальти защитывается программе как процессорное время?
Андрей Светлов
Янв. 9, 2011 20:35:46
asilyator
А пенальти защитывается программе как процессорное время?
Как пропуск тактов конвейером. Детали сильно отличаются в разных реализациях.