Как я понял, у нас на форуме есть действующие программисты. :)
Ищу сабж. Пока безрезультатно. Где рыть?
На примере? Не воткну.
http://computers.plib.ru/programming/Assembler/Pr/Index7.htm
Цитата: myst от апреля 14, 2009, 19:59
Как я понял, у нас на форуме есть действующие программисты. :)
Ищу сабж. Пока безрезультатно. Где рыть?
В смысле, наибольшую общую подстроку двух строк?
Цитата: "O" от
http://computers.plib.ru/programming/Assembler/Pr/Index7.htm
Ну зачем же сразу в клуп садо-мазо-то отправлять? ;D
Объясняю. :)
Есть, значит, у нас список строк: предприниматель, законодатель, предстать, верстать, устать.
Нужна функция, выдающая список общих частей, а также информацию, у скольких строк данная общая часть встречается. В нашем случае это будут: пред (2), атель (2), стать (3).
Примерно так. :)
man grep
Если массивы данных не большие - всё просто, почарово сравнивать, не вижу проблемы.
Если массивы гигабайтные, то там да, без мудрёного алгоритма не обойтись :)
Цитата: Алексей Гринь от апреля 14, 2009, 20:37
почарово сравнивать
Настоящие лингвисты не работают с однобайтными кодировками! 8) ::)
Цитата: "O" от
Настоящие лингвисты не работают с однобайтными кодировками! 8) ::)
У настоящих лингвистов чар определён в 2-4 байта 8)
В C# например так.
Цитата: Алексей Гринь от апреля 14, 2009, 21:13
В C# например так.
Но ведь писателю на С# не нужно искать никаких алгоритмов. Пользуются теми, которые зашиты в библиотеку, а другими — не положено! :green:
Цитата: "O" от
Но ведь писателю на С# не нужно искать никаких алгоритмов. Пользуются теми, которые зашиты в библиотеку, а другими — не положено!
С чего это вдруг? Что за бред?
Цитата: Алексей Гринь от апреля 14, 2009, 21:33
С чего это вдруг? Что за бред?
Ага, смайликов не замечаем, да? :)
Цитата: "O" от
Ага, смайликов не замечаем, да? :)
Не нужно искать алгоритмы, если во фреймворке нет даже класса Set, оный наличествует в большинстве библиотек общего назначения для "хацкерного" СиПоПа?
8)
Не очень просто понимаю юмор фразы. Практически у всех языков есть стандартные библиотеки с уже готовыми алгоритмами. СиШарп не исключение.
Цитата: "злой" от
man grep
Подробнее, пжалста. Возможно, я не умею его готовить. :???
Цитата: "Алексей Гринь" от
Если массивы данных не большие - всё просто, почарово сравнивать, не вижу проблемы.
Это ж не просто сравнение. Да и изобретать самокат тоже лень. Хочется готовенького. :)
Цитата: myst от апреля 14, 2009, 20:20
Объясняю. :)
Есть, значит, у нас список строк: предприниматель, законодатель, предстать, верстать, устать.
Нужна функция, выдающая список общих частей, а также информацию, у скольких строк данная общая часть встречается. В нашем случае это будут: пред (2), атель (2), стать (3).
Примерно так. :)
Но ведь здесь есть много других подстрок, например, -пр-.
Цитата: "GaLL" от
Но ведь здесь есть много других подстрок, например, -пр-.
Я же не робат — всё не углядел. :)
Длину кусочков я планирую задавать в параметрах.
Просто постановка задачи неясна. :) И, как правильно заметил Алексей Гринь, важен объем обрабатываемой информации.
Цитата: myst от апреля 14, 2009, 22:19
Длину кусочков я планирую задавать в параметрах.
Если, например, надо посчитать статистику для кусков конкретной длины k, то это можно эффективно сделать при помощи хэширования. Получится линейный относительно суммарной длины всех слов алгоритм.
Цитата: "GaLL" от
Просто постановка задачи неясна. :)
Как?! Всё ещё не ясна?!
Цитата: "GaLL" от
И, как правильно заметил Алексей Гринь, важен объем обрабатываемой информации.
Размер входного списка около 70 000 слов.
Цитата: "GaLL" от
Если, например, надо посчитать статистику для кусков конкретной длины k, то это можно эффективно сделать при помощи хэширования. Получится линейный относительно суммарной длины всех слов алгоритм.
Так-так! А подробнее? :)
Цитата: "myst" от
Размер входного списка около 70 000 слов.
Это для себя нужно?
Если так, могу набросать быдлоалгоритм, который будет работать долго, но сделает своё дело :)
Цитата: "Алексей Гринь" от
Это для себя нужно?
Да.
Цитата: "Алексей Гринь" от
Если так, могу набросать быдлоалгоритм, который будет работать долго, но сделает своё дело :)
Я и сам могу набросать, была бы идея. :)
Цитата: "myst" от
Я и сам могу набросать, была бы идея. :)
Ждите :D
Вырезаете из каждого слова всевозможные куски длинной не меньше, чем вам нужно, и добавляете их в хеш-таблицу (Hashtable/Dictionary в C#, hash_map в C++), где ключ - это сама подстрока, а значение - её встречаемость.
И потом пробегаетесь по хеш-таблице и отображаете её содержимое.
Цитата: "svarog" от
Вырезаете из каждого слова всевозможные куски длинной не меньше, чем вам нужно
Скока ж памяти и времени всё это вырезать
нужны inplace сравнивания, и уже когда нужно - вырезания в хеш, что я щас иделаю
Цитата: "svarog" от
Вырезаете из каждого слова всевозможные куски длинной не меньше, чем вам нужно, и добавляете их в хеш-таблицу (Hashtable/Dictionary в C#, hash_multimap в C++), где ключ - это сама подстрока, а значение - её встречаемость.
Так и сделаю. Спасибо.
Цитата: "myst" от
Так и сделаю. Спасибо.
На чём собираешьтеся?
Цитата: "Алексей Гринь" от
Скока ж памяти
Не больше 100 мегабайт, я думаю.
Цитата: "Алексей Гринь" от
На чём собираешьтеся?
На чём обычно — на clisp'е. Если будет сильно тормозит, на жабе перепишу. :)
собираешьтеся — это политкорректный вариант? ;D
Цитата: "Алексей Гринь" от
Скока ж памяти и времени всё это вырезать
нужны inplace сравнивания, и уже когда нужно - вырезания в хеш, что я щас иделаю
хотя нет, в сишарпе не прокатит, обращение к чару из строки слишком дорогое в НЕТе удовольствие :(
Цитата: "myst" от
собираешьтеся — это политкорректный вариант? ;D
угу
Цитата: "myst" от
На чём обычно — на clisp'е. Если будет сильно тормозит, на жабе перепишу. :)
короче, давайешьте (:)) конкурс - я пишу свою версию, постишь базу, и засекаем у кого по времени быстрее
Цитата: "Алексей Гринь" от
короче, давайешьтеся (:)) конкурс - я пишу свою версию, постишь базу, и засекаем у кого по времени быстрее
Сравнение эффективности хэшей в C#, CLISP и Java? ;)
Цитата: "myst" от
Сравнение эффективности хэшей в C#, CLISP и Java?
ну и алгоритмов - я не буду заниматься вырезанием в память всех возможных комбинаций, только тех, что нужно
Базу прошу сразу залить куда-нибудь, я возможно скоро готов )
Не, я пас, всё таки обращение к строкам в НЕТе очень медленное :(
Трогать сипопу неохота.
Цитата: "Алексей Гринь" от
ну и алгоритмов - я не буду заниматься вырезанием в память всех возможных комбинаций, только тех, что нужно
А каких нужно? :)
Цитата: "myst" от
А каких нужно?
сравниваются строки без выделений памяти и если находится общее, вырезается и суётся в хештаблицу
это для тех, кто памятью бережёт
правда, реализация получилась оч медленная -- а оптимизиорвать в лом
посмотрим как выйдет у вас)
Цитата: "Алексей Гринь" от
Базу прошу сразу залить куда-нибудь, я возможно скоро готов )
Список слов: http://www.artint.ru/projects/frqlist/words.num.zip
Цитата: "Алексей Гринь" от
посмотрим как выйдет у вас)
Мы вроде перешли на ты, нет?
Цитата: Алексей Гринь от апреля 15, 2009, 00:04
правда, реализация получилась оч медленная -- а оптимизиорвать в лом
Это вы перемудрили :) Я только что реализовал тот простейший вариант что описывал, 10 строчек кода и работает мгновенно.
Вот верхняя часть таблицы результатов для подстрок длинной десять:
ологически 34
аспростран 31
распростра 31
интересова 30
значительн 29
станавлива 29
ительность 28
ологическо 25
следовател 25
определенн 24
сопровожда 24
соответств 23
государств 22
представля 22
естественн 21
обыкновенн 21
иологическ 20
офессионал 20
профессион 20
рофессиона 20
Неинтересная статистика, потому что в базе идут вместе со словом и его словоформы -- они, группируясь, и дают высокую встречаемость.
myst, а для чего это, если не секрет? :)
На CLISP'е ≈50 секунд (в месте с выводом) и <30 Мбайт памяти. Я думал будет гораздо хуже. :)
Цитата: "svarog" от
Неинтересная статистика, потому что в базе идут вместе со словом и его словоформы -- они, группируясь, и дают высокую встречаемость.
Самая что ни на есть интересная. :) Правда, мне ещё надо частоту словоформы учесть, но это ерунда.
Цитата: "svarog" от
myst, а для чего это, если не секрет? :)
Я занимаюсь машинописью по одной методичке. Возникли у меня сомнения в оптимальности упражнений на «слоги». Всё-таки написана она была четверть века назад.
Цитата: myst от Я занимаюсь машинописью по одной методичке. Возникли у меня сомнения в оптимальности упражнений на «слоги». Всё-таки написана она была четверть века назад.
А , тогда, если я правильно понимаю, можно просто идти по тексту, вырезая из каждого слова подстрочки и складывая их в хеш-таблицу.
Цитата: svarogдля подстрок длинной десять
Ух, гадкое слово. :-[
Цитата: "svarog" от
А , тогда, если я правильно понимаю, можно просто идти по тексту, вырезая из каждого слова подстрочки и складывая их в хеш-таблицу.
Не, задача — отобрать самые частотные кусочки слов и сделать из них упражения. В общем-то, она уже почти решена. :)
Ну, так и есть - если кусочки выдирать сразу из текста, а не из базы слов, то частотность их в тексте учитывается автоматически.
Цитата: "svarog" от
Ну, так и есть - если кусочки выдирать сразу из текста, а не из базы слов, то частотность их в тексте учитывается автоматически.
Эта база слов — частотный словарь. В нём данные о частотности слов уже есть.
Понятно. И как, в методичке правильные упражнения? :)
Цитата: svarog от апреля 15, 2009, 18:16
Понятно. И как, в методичке правильные упражнения? :)
У меня тут грабли с таблицей стилей форума вылезли... :wall: Руки до полученной статистики ещё не дошли. :)
Цитата: "svarog" от
Это вы перемудрили :) Я только что реализовал тот простейший вариант что описывал, 10 строчек кода и работает мгновенно.
Вот верхняя часть таблицы результатов для подстрок длинной десять:
ну так у вас для постоянной длины
я писал для разных длин, указывается лишь минимальный размер
Цитата: "Алексей Гринь" от
я писал для разных длин, указывается лишь минимальный размер
У меня ок. 50 секунд и чуть меньше 30 Мбайт. :)
Цитата: Алексей Гринь от апреля 16, 2009, 01:18
ну так у вас для постоянной длины
я писал для разных длин, указывается лишь минимальный размер
У меня мгновенно (<0.5 сек) для разных длин тоже (минимальный размер указывал 3).
Цитата: "svarog" от
У меня мгновенно (<0.5 сек) для разных длин тоже (минимальный размер указывал 3).
На том же списке?
У меня по всем длинам считала (от 1 буквы до слова целиком).
Какой расход памяти?
Да, инструмент-то у Вас какой? :)
.Net, C#
Поставил мин. длину подстроки один.
~ 2 сек и 50 MB
я жадный до памяти чо-т
в следующий раз не буду жалеть
Цитата: "svarog" от
.Net, C#
Поставил мин. длину подстроки один.
~ 2 сек и 50 MB
А железо какое?
Вы мяне нібыта падазраяцё ў нейкіх хітрыках :green:
Celeron 1.4Ghz
Цитата: "svarog" от
Вы мяне нібыта падазраяцё ў нейкіх хітрыках :green:
Celeron 1.4Ghz
Да нет, хочу прикинуть во сколько раз байткодовая машина CLISP'а медленнее шарпового JIT'а.
Чтобы не гадать, Вы бы не могли мне дать исходник? :)
Прямо сюда выложить, да.
Пожалуйста. :)
http://pastebin.com/m6b91ab85
(обращаю внимание, что больше времени отнимает сортировка полученного результата, чем само раскладывание в хеш)
Хех, всё сразу -- и йилды, и лямбды :)
гыгы ну да, выпендрился
но ведь всё к месту пришлось? :)
Цитата: "svarog" от
http://pastebin.com/m6b91ab85
Она под какой дотнет? :what: Компилятор от третьего (точнее, от второго) на синтаксис ругаецца. :(
Цитата: "myst" от
Компилятор от третьего (точнее, от второго)
типа это одно и то же?
C#3 воркает без проблем
Цитата: "Алексей Гринь" от
типа это одно и то же?
Дык, там компилятор в каталоге «v2.0.50727» какбэ намекает. :) Или у меня какой-то неправильный .NET 3... :??? Или нужен ещё какой-то .NET?
Понятно, нужен другой дотнет — 3.5. :wall:
Ошибки бы привёл какие пишет.
P.S. А, лямблы скорей всего не понимает, это где "=>", заменить на анонимный делегат потребно.
P.P.S. Запутал. Версия СиШарпа какая? %)
Да, и yield'ы не поймёт, и var-ы не поймёт - это в 3.0 появилось.
сейчас перепишу
Цитата: "svarog" от
Да, и yield'ы не поймёт
Не, йилды во втором уже были
Цитата: "Алексей Гринь" от
P.P.S. Запутал. Версия СиШарпа какая? %)
У меня .NET Framework 3.0, а надо .NET Framework 3.5.
переписал :)
http://pastebin.com/m7f7fb367
Цитата: "myst" от
У меня .NET Framework 3.0, а надо .NET Framework 3.5.
блин версия сишарпа от фреймворка не зависит нифига
может писать на C#2 под Framework 3.0, а можешь на C#3 под Framework 2.0
я в коде не заметил чисто Framework3.5шных функций
Цитата: "svarog" от
переписал :)
http://pastebin.com/m7f7fb367
О! Thank you very much! :yes:
Цитата: "Алексей Гринь" от
блин версия сишарпа от фреймворка не зависит нифига
может писать на C#2 под Framework 3.0, а можешь на C#3 под Framework 2.0
А компилятор для С# 3 где брать?
Цитата: http://en.wikipedia.org/wiki/C_Sharp_(programming_language)#Features_of_C.23_3.0
C# 3.0 was released on 19 November 2007 as part of .NET Framework 3.5.
Ы?
Цитата: Алексей Гринь от апреля 17, 2009, 14:03
Цитата: "svarog" от
Да, и yield'ы не поймёт
Не, йилды во втором уже были
точно! а мы и не знали :D
У меня почему-то
Цитировать
./parts-freq2 0.01s user 0.01s system 0% cpu 5.119 total
Хотя процессор 1,6 ГГц, второй прогон... :???
Цитата: "myst" от
Цитировать# 3.0 was released on 19 November 2007 as part of .NET Framework 3.5.
Ы?
и чо?
я отдельно где-то качал и быдлокодил на C#3 под .NET 2.0 и VS2005
а может я фантазирую, но в любом случае ничто не мешает дружбе C#3 и .NET 2.0 (Linq тока добавить), ибо технически .NET 2.0 = .NET 3.0 = .NET 3.5 плюс в C#3 добавлен один лишь синтактический сахар
ЦитироватьХотя процессор 1,6 ГГц, второй прогон... :???
Я обращал внимание, что там половина времени - сортировка для вывода
(сортирую по длине подстроки, с одинаковой длиной - по частотности, а с одинаковой частотностью - в алфавитном порядке)
Цитата: "Алексей Гринь" от
я отдельно где-то качал и быдлокодил на C#3 под .NET 2.0 и VS2005
Хде? Я тожа хочю. :)
Цитата: "svarog" от
Я обращал внимание, что там половина времени - сортировка для вывода
Так Ваши данные без сортировки были?
У меня без сортировки 2,56 сек.
Цитата: "myst" от
Хде? Я тожа хочю.
Возможно, у меня всё в голове перемешалось.
Цитата: myst от апреля 17, 2009, 14:17
Так Ваши данные без сортировки были?
У меня без сортировки 2,56 сек.
Т.е. остальные 50 сек занимала сортировка? :o
Я там сообщения на консоль вывожу: когда начинается чтение из файла, когда складывание в хеш-таблицу, и когда полученная хеш-таблица сортируется для вывода результата. Всё вместе секунд 5-6 занимает.
Цитата: "svarog" от
Т.е. остальные 50 сек занимала сортировка? :o
;D Да я про Ваш код, про Ваш.
У Вас в выхлопе нет однократно встречаемых сочетаний. А их там (по моей программе) 234 682.
А, да-да, мои данные были без сортировки. И секунды оценивались "на глазок" (чем вы их кстати меряете?)
ЦитироватьУ Вас в выхлопе нет однократно встречаемых сочетаний.
нету... потому что там стоит if (de.Value > 1), если убрать if - то будут.
btw я так понял, в вашем файле words.num вторым значением идёт частотность слова в тексте, и на неё ещё нужно умножить?
Цитата: "svarog" от
(чем вы их кстати меряете?)
Шелловский time.
Цитата: "svarog" от
нету... потому что там стоит if (de.Value > 1), если убрать if - то будут.
Это не сильно повлияло: 2,957 сек. :)
Мда, CLISP педальный. Будем ждать, когда прикрутят JIT. :)
Вот, прикрутил ещё учёт частотности слова (из файла words.num)
http://pastebin.com/m5cc32000
Цитата: "svarog" от
Вот, прикрутил ещё учёт частотности слова (из файла words.num)
У меня исключение вылетает: ошибка преобразования строки в вещественное число. Десятичная точка ему нелюба?
Думаю да.
у вас наверно русская локаль по умолчанию, с разделитем-запятой.
Исправил код чтобы учитывалась точка:
http://pastebin.com/m65bc53d3
Цитата: "svarog" от
Исправил код чтобы учитывалась точка:
http://pastebin.com/m65bc53d3
Цитироватьparts-freq3.cs(25,71): error CS0103: The name 'NumberStyles' does not exist in the current context
:???
Я ещё добавил вверху using System.Globalization; :)
Но не подсветил эту строчку.
Кстати, можно задать остальным лингвофорумчанам загадку: какое двух- и трёх- буквенное сочетание наиболее частое в русском языке (на основе вашего текста).
Про то, что самая частая буква это "о" - наверно все знают. (Она и на русской клавиатурной раскладке, сделанной по частотному принципу, как раз в серединке) :)
Цитата: "svarog" от
Я ещё добавил вверху using System.Globalization; :)
Ага, исправил. Оттранслировалось, но исключение всё равно вылетает. :what:
Цитата: "svarog" от
(Она и на русской клавиатурной раскладке, сделанной по частотному принципу, как раз в серединке)
Кстати, на основе этих данных можно сочинить более оптимальную раскладку. :)
Цитата: myst от апреля 17, 2009, 15:19
Ага, исправил. Оттранслировалось, но исключение всё равно вылетает.
Ыыы не силён я в глобализации. :what:
Цитата: "svarog" от
Ыыы не силён я в глобализации.
Может, проще локаль в программе выставить?
Вот так должно заработать:
http://pastebin.com/m60c6deb2
(изменил ту же строчку, подсвеченную)
Цитата: "svarog" от
Вот так должно заработать:
http://pastebin.com/m60c6deb2
(изменил ту же строчку, подсвеченную)
Работает. :up:
Расчёты слегка не сходятся. :what:
Цитата: мой
1 о 520495.560
1 е 394971.970
1 а 364186.940
1 и 316215.200
1 т 298034.720
1 н 296227.800
1 с 250330.580
1 л 225885.580
1 в 203667.170
1 р 200226.330
1 к 160883.810
1 м 145472.270
1 д 144115.360
1 у 131469.620
1 п 129564.516
...
Цитата: Ваш
о 520415,64
е 394906,10
а 364115,20
и 316148,20
т 297991,75
н 296170,80
с 250336,64
л 225890,18
в 203672,42
р 200231,02
к 160887,59
м 145476,53
д 144117,09
у 131471,56
п 129566,36
...
Ого :what: А почему? Разница-то существенная.
Цитата: "svarog" от
А почему?
:donno: Считают по-разному. Надо сравнивать...
На первый взгляд, вроде то же самое. :???
Вспоминается классическое "Компьютер делает не то, что ты от него хочешь, а то, что ты ему прикажешь".
Сломал мозг, но так и не понял, в чём разница. :wall: Отличаются только 244 строки результатов из 397 004. :???
ЦитироватьШелловский time.
стартап рантайма засчитывается, а это не хорошо
Цитата: "svarog" от
И секунды оценивались "на глазок" (чем вы их кстати меряете?)
var ticks = Environment.TickCount;
...
var secs = new TimeSpan(Environment.TickCount - ticks);
Цитата: "Алексей Гринь" от
стартап рантайма засчитывается, а это не хорошо
В командной строке как раз интересно полное время работы команды. Да и временем стартапа, начиная со второго прогона, можно пренебречь.