Андрей Светлов
Дек. 30, 2010 10:23:13
with open(outfile, 'w') as dst:
used = set()
for line in open(filename, 'r'):
if line not in used:
used.add(line)
dst.write(line)
Ваш поиск на повторы, наверное, самый медленный из всех возможных.
Процессор не может разогнаться из-за перманентного промаха в кэш.
baragoz
Дек. 30, 2010 10:37:43
Спасибо большое, погуглил по Вашему ответу, вроде понял про промах и попадание. И почему проц не работал “на всю катушку”.
А “used = set()” это собственно данные файла? Чет не могу въехать ни как в код.
Да медленный =) полтора часа файл перебирал…
Андрей Светлов
Дек. 30, 2010 10:41:56
used - множество уже записанных строк. Если новая строка уже есть в used - получаем дубликат, который нужно пропустить.
Множество организовано как хэш таблица - поэтому поиск в нем гораздо быстрее чем по списку.
baragoz
Дек. 30, 2010 10:54:47
Спасибо за внимание.
Туда ли я попал?
http://ru.wikipedia.org/wiki/Хеш-таблицаЯ правильно понимаю, что для каждой строки вычисляется хеш как индекс и потом проверяется нет ли элементов с одинаковыми индексами? Т.е. строка - ключ, хеш от ключа - индекс.
baragoz
Дек. 30, 2010 11:15:23
Полтора часа против трех секунд… Я в шоке… Я не хочу просто взять код. Хочу понять как работает.
————-ADD————
файл из 2 000 000 строк (скопировал файл несколько раз) за секунду!!! Сча себя таким быдлокодером ощущаю, что хочется пальцы сломать.
————-ADD————
поправочка - в первый раз меньше чем за секунду пробежал (не туда посмотрел).
Андрей Светлов
Дек. 30, 2010 11:19:11
Да. Хэш-таблицы могут быть устроены чуть по разному (в Питоне - Кнут, вариант D).
Главное - у них константное время доступа.
В результате мой вариант имеет линейную сложность (одна пробежка по файлу, хэш константный).
Ваш - квадратичный (цикл по строкам, внутри которого .count делает еще одну пробежку).
Ну и попадание в кэш, да. Выяснение факта, что строка не находится в хэш-таблице - требует меньшего числа чтений страниц памяти. Для больших объемов разница может быть заметна.
Андрей Светлов
Дек. 30, 2010 11:24:22
baragoz
Полтора часа против трех секунд…
Не переживайте. Я подобную задачку впервые делал много лет назад. Окружающие тоже были изрядно удивлены.
o7412369815963
Дек. 30, 2010 11:29:37
Андрей Светлов
with open(outfile, 'w') as dst:
так, имхо, оптимальнее
used = set()
for line in with open(filename, 'r'):
used.add(line)
dst = open(outfile, 'w'):
dst.writelines(iter(line))
+ нет лишней проверки вхождения
+ запись охапкой (хотя не факт что внтури охапка реализована)
Андрей Светлов
Дек. 30, 2010 11:31:51
А где ваш порядок строк?
o7412369815963
Дек. 30, 2010 11:37:18
Андрей Светлов
А где ваш порядок строк?
а он нужен? если да, тогда этот алгоритм не подойдет.