VBNet - Форум - Ночь, улица, фонарь, аптека..

Вопрос: Ночь, улица, фонарь, аптека.. Добавлено: 16.04.09 21:43

Автор вопроса: gekko | Web-сайт: kalamfur.ru

Товарищи!

Требуется из текста выбрать 50 наиболее часто встречающихся слов (и выстроить в порядке убывания).
Текст - килобайт 200-300.

Кто знает, как это сделать с наибольшей скоростью?
Ответить

Ответы Всего ответов: 7

Номер ответа: 1 Автор ответа: Smith ICQ: adamis@list.ru Вопросов: 153 Ответов: 3632	Профиль \| \| #1	Добавлено: 16.04.09 22:06
	Полюбому придется все слова перебирать, а быстрее всего это сделает асм и правильный алгоритм. Ответить

Номер ответа: 2 Автор ответа: Morpheus Вопросов: 224 Ответов: 3777	Web-сайт: xury.zx6.ru Профиль \| \| #2	Добавлено: 16.04.09 22:20
	хз как на васике, но на перле\пхп яб делал так: Создать хеш-таблицу со именем ключей из слов и вначале выставить значение = 0. то есть типа Words{"telecommunication"} = 0; потом сплитом по пробелу или чему там вогнать все слова в массив строк (не забыв избвиццо от точек, запятых и прочей муры -- регескепами, например), перебрать его, и на каждое слово либо создавать новый элемент хеш-таблицы или делать ++ на уже существующий.. Проблема будет с выбором 50 частых слов... можно отсортировать каким нить алгоритмом слияния; тогда большая-тета будет = n * log n, но мне кажется можно проще. у кого есть идеи? Ответить

Номер ответа: 3 Автор ответа: gekko Вопросов: 39 Ответов: 127	Web-сайт: kalamfur.ru Профиль \| \| #3	Добавлено: 17.04.09 15:24
	Сделал на Васике, но ОЧЕНЬ медленно выполняется. Буду пробовать на PHP. Нашел вот такую прогу, в ней схожее реализованно, но срабатывает напорядок быстрее моего кода на VB. Не думаю чтоб на астме писали. http://slil.ru/27459208 Ответить

Номер ответа: 4 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979	Web-сайт: sharpc.livejournal.com Профиль \| \| #4	Добавлено: 17.04.09 15:42
	А зачем тут что-то мутить с сублинейнологарифмическими алгоритмами? Решение на PHP прямо в лоб работает на 500КБ 0.5 секунд. $f = file_get_contents("Generation P.txt"); preg_match_all('@(\W\|^)(\w+)(\W\|$)@is', $f, $m); $wc = array(); foreach ($m[2] as $word) { $w = strtolower($word); if (array_key_exists($w, $wc)) ++$wc[$w]; else $wc[$w] = 1; } arsort($wc); Ответить

Номер ответа: 5 Автор ответа: Morpheus Вопросов: 224 Ответов: 3777	Web-сайт: xury.zx6.ru Профиль \| \| #5	Добавлено: 17.04.09 15:56
	Ugu, ya pro sortirovku bil ne uveren... ya b zabil v mysql i sprosil select * from words order by number desc limit 50; ili kak tam :D Ответить

Номер ответа: 6 Автор ответа: Morpheus Вопросов: 224 Ответов: 3777	Web-сайт: xury.zx6.ru Профиль \| \| #6	Добавлено: 17.04.09 17:59
	А что делает arsort($wc); ? Сортирует? Может сделать 50 проходов и выбрать 50 самых поп. слов? сложность тогда будет линейной... Ответить

Номер ответа: 7 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979	Web-сайт: sharpc.livejournal.com Профиль \| \| #7	Добавлено: 17.04.09 23:26
	MySQL при построении индекса как раз и выполняет сортировку, амортизированно O(NlogN). arsort сортирует в обратном порядке, сохраняя ключи. 50N для любого разумного N больше, чем NlogN. Ответить

Страница: 1 |