![]() |
|
![]() ![]() ![]() |
|
14SatanA88 |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 393 Регистрация: 13.5.2010 Репутация: 1 Всего: 5 |
Доброго времени суток, уважаемые программеры.
Предыстория: Не так давно, исходя из утверждений одного знакомого мне человека, решил выяснить, где же быстрее всего считается частота слов в тексте. Просто интересно стало. Но так как программист я хреновый, подумал, что не лишним будет создать тему на форуме. Входные данные: У нас есть файл с текстом, содержаший только латиницу (чтобы не заморачиваться с кодировками). Выходные данные Опять же текстовый файл, содержащий пары "слово = частота" в алфавитном порядке, разделенные переводом строки. Некоторые замечания: Будем считать словом последовательность символов из диапазона [a-zA-Z] (только буквы латинского алфавита, никаких апострофов и дефисов). Регистр символов не важен. Я взял для примера оригинал "Противостояния" Стивена Кинга (~2.5 Mb). Он лежит в аттаче. Время считается только на стадии подсчетов. То есть получение текста из файла / запись результатов / сортировка хеша по ключам не важны. Смысл создания темы: Далее я приведу исходный код сабжа на нескольких ЯП и результаты тестирования на моей машине. Я прошу Вас взглянуть на код, сказать, где можно что-либо исправить, дабы ускорить его. Ну и было бы превосходно сопроводить замечания подробными комментариями. Некоторым может быть не интересно, и поэтому прошу не оставлять бессмысленных постов. Критика же приветствуется. С++ (среднее время = 646 ms) Java (среднее время = 605 ms)
Perl (среднее время = 224 ms)
PHP (среднее время = 307 ms)
Python (среднее время = 1448 ms)
Файлы с исходными кодами, а так же пример входного и выходного файла в аттаче. P.S. Судите строго. Это сообщение отредактировал(а) 14SatanA88 - 26.10.2012, 16:27 Присоединённый файл ( Кол-во скачиваний: 23 ) ![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Akina |
|
|||
Советчик ![]() ![]() ![]() ![]() Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Аттача-то и не подвезли... небось не заархивировал, прежде чем аттачить?
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
disputant |
|
|||
![]() Бывалый ![]() Профиль Группа: Участник Сообщений: 210 Регистрация: 28.11.2011 Репутация: 2 Всего: 3 |
Не силен в остальных языках, на код C++ оставил впечатление "зачем просто, если можно сложно?!"
|
|||
|
||||
Silent |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 252 Регистрация: 3.10.2006 Репутация: 1 Всего: 9 |
Сильно возмутился я представленным цифрам, и решил проверить на деле - "за державу обидно" (за С++ то есть). Каким компилятором получен результат? учитывая присутствующий заголовочный файл <dos> и тег C++ Builder - предполагаю, что в сильно бородатом borland c++ 3.1, так? Ужас =)
Вот мои результаты (среднее время по пяти замерам):
Размер тестового файла был 2,5Мб. Платформа i3, 2Gb, debian 6 (WinXP для C#) на Java решение не тестил, но мое мнение - она не должна выйти за 300-350мс, все решения тестировались "как есть" Прилагаю исходники на C# и Golang:
Golang:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
maxim1000 |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
ещё стоит проверить, одинаковые ли алгоритмы
если Perl, например, использует хеш-контейнер, имеет смысл его использовать во всех языках -------------------- qqq |
|||
|
||||
disputant |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() Бывалый ![]() Профиль Группа: Участник Сообщений: 210 Регистрация: 28.11.2011 Репутация: 2 Всего: 3 |
Приведенный исходник C# - 172 тика. C++ с исправленными ошибками - 130 тиков. (Visual Studio 2010)
Но если отказаться от string'ов и этой жуткой проверки, то примерно 89 тиков
Как я понимаю, если задача получить именно список слов с частотами, а не конкретно map, то можно и еще ускориться... P.S. В 3.1 STL еще не было ![]() Это сообщение отредактировал(а) disputant - 25.10.2012, 16:52 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
_Y_ |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1651 Регистрация: 27.11.2006 Репутация: 8 Всего: 34 |
14SatanA88, подумал попробовать, но не нашел файла данных, т.е. самого текста. Где он лежит?
-------------------- Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:) |
|||
|
||||
disputant |
|
|||
![]() Бывалый ![]() Профиль Группа: Участник Сообщений: 210 Регистрация: 28.11.2011 Репутация: 2 Всего: 3 |
Ну, я, например, взял тут |
|||
|
||||
14SatanA88 |
|
||||||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 393 Регистрация: 13.5.2010 Репутация: 1 Всего: 5 |
аттач подвез. там исходные коды всего что я понаписал, выходной и выходной файлы
В почти таком же бородатом Borland c++ 5.02 (кстати, посоветуйте компилятор под Windows) наверное, стоит сказать, на какой машине проверялись коды: i7, 6Gb, Win7
на самом деле здесь важна скорость работы алгоритма. то есть используем любые средства языка, лишь бы добиться максимальных показателей скорости disputant, Вам отдельное спасибо за приведенный пример. Было бы превосходно, если бы Вы вкратце написали суть алгоритма. И о map я считал, что в данной задаче это идеальный вариант. |
||||||
|
|||||||
disputant |
|
|||
![]() Бывалый ![]() Профиль Группа: Участник Сообщений: 210 Регистрация: 28.11.2011 Репутация: 2 Всего: 3 |
Суть алгоритма - раз мы все равно втянули весь текст в память, зачем его копировать? Сразу весь преобразовали в нижний регистр, и пошли сканировать в нем слова, обрезая их (все равно между словами что-то есть, что можно безболезненно превратить в 0), так что каждое слово просто представлено указателем на место в памяти. map хранит эти указатели, но сравнивает их между собой лексикографически, как строки. Как минимум избавляемся от массы накладных расходов string. С заменой map сильно не думал, но можно попробовать взять что-то не такое универсальное, но быстрое - например, какую-нибудь хэш-таблицу, или, например, матрицу 26x27 по первым двум буквам, а в ней какие-то списки или еще что - все-таки слова обычно достаточно короткие... В общем, тут уже надо поэкспериментировать. Первый напрашивающийся вариант - собрать все в один вектор и отсортировать - из-за большого количества повторений может и не обогнать map (так что для разных текстов могут быть оптимальны разные варианты). |
|||
|
||||
volatile |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 2 Всего: 85 |
||||
|
||||
14SatanA88 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 393 Регистрация: 13.5.2010 Репутация: 1 Всего: 5 |
Спасибо за ответы касательно Си. Хотелось бы еще увидеть что-то относительно других ЯП.
|
|||
|
||||
volatile |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 2 Всего: 85 |
Решил я тоже за державу свои 5 копеек внести.
Ну что-ж, раз любые средства, давайте попробуем. За основу взял алгоритм disputantа, заменил стандартный мап, на бустовский хеш-анордеред.
Итого такие результаты: Буду писать в процентах, чтобы голову не забивать, цифры все равно у всех разные. За 100% взял самый быстрый показатель ТС
Была мысль еще свой хеш-мап написать быстренько, простенький, но заточенный под это дело, но подумал что и так не плохо. (может еще напишу, если настроение будет.) Еще неплохо бы собрать на интеловском компилере. Так что резервы у С++ еще есть. =) 14SatanA88, могу выложить егзешник, если запустите на своем "калиброванном" компе. 14SatanA88, Другие языки пока отдыхают. ![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
14SatanA88 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 393 Регистрация: 13.5.2010 Репутация: 1 Всего: 5 |
volatile, премного благодарен Вам за проделанную работу. Если Вы еще под настроение напишете свой хеш, с блэкджеком и плюшками, будет вообще круто.
я чего завел вообще тему. предмет разговора был в том, что якобы java быстрее всего сделает сабж. я же предположил что perl будет быстрее (честно признаюсь, на момет разговора вообще perl знал только по работе с regexp). ну и потом мне стало интересно, и я понаписал то что смог ![]() P.S. Еще вернусь к тому, о чем спрашивал: посоветуйте компилятор для C++ под Win7 |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |