Перейти к содержимому

7

В процессе решения задачи быстрого подсчета частот совместных появлений слов в тексте создал интересную структуру данных, которая также позволяет вычислять частоты появления первого слова проверяемой пары, а также эта структура строит префиксное дерево, которое может быть использовано в последующем анализе текста.

Исходный код доступен на GitHub: github.com/Maxime2/cooccurrences

Когда вы выполните команду make, вы должны увидеть такой вывод:


cc -O3 -funsigned-char cooccur.c -o cooccur -lm

Example 1
./cooccur a.txt 2 < a.in | tee a.out

Checking pair d e
Count:3  cocount:3
Relative frequency: 1.00

Checking pair a b
Count:3  cocount:1
Relative frequency: 0.33


Example 2
./cooccur b.txt 3 < b.in | tee b.out

Checking pair a penny
Count:3  cocount:3
Relative frequency: 1.00

Checking pair penny earned
Count:4  cocount:1
Relative frequency: 0.25

Программа cooccur принимает два аргумента: имя файла для обработки и размер окна слов, в котором считаются частоты совместного появления. После обработки текста и заполнения этой структуры данных, программа считывает пары слов со стандартного файла ввода, по одной паре на строку, и подсчитывает частоту появления первого слова пары в текста и частоту совместного появления в тексте указанной пары слов в пределах заданного окна. Если второе слово встречается более одного раза в окне, только первое появление учитывается.

Примеры взяты отсюда:

1

Если у вас сайт на попечении, сделайте его пригодным для мобильных. Для этого в большинстве случаев достаточно додавить в head такую мету:


<meta name="viewport" content="width=device-width, initial-scale=1">

И Гугол вас не забудет - намек, что он учитывает дружественность к мобильным при ранжировании.

Проверить дружественность вашего сайта к мобильным устройствам можно здесь: //www.google.com.au/webmasters/tools/mobile-friendly/.

Ненайдя промышленной реализации метода сортировки bottom-up heapsort, решил реализовать этот алгоритм самостоятельно, с небольшой модификацией.

Исходный код можно посмотреть на Github: github.com/Maxime2/heapsort

Bottom-up heapsort (bottom-up-heapsort) является вариантом алгоритма сортировки heapsort (пирамидальной сортировки) с новой процедурой восстановления пирамиды. Этот варианд превосходит, в среднем, алгоритм быстрой сортировки (quicksort), если n > 2400, и модифицированный вариант быстрой сортировки с выбором ведущего элемента как медианы 3 элементов массива, если n > 16000.

Алгоритм bottom-up heapsort описан в работе Ingo Wegener, BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small), Theoretical Computer Science 118 (1993), pp. 81-98, Elsevier.

Добавленная мной модификация, позволяющая дополнительно сэкономить (n-2)/2 операций обмена и (n-2)/2 операций сравнения, при n > 3, основана на идее отложенного восстановления пирамиды после перемешения корневого элемента на его место, найденной в работе D. Levendeas, C. Zaroliagis, Heapsort using Multiple Heaps, in Proc. 2nd Panhellenic Student Conference on Informatics -- EUREKA. – 2008. – P. 93–104.

3

Лекция "Настройка вашего сервера PostgreSQL" (Tuning your postgresql server) на Linux Conf Australia 2011 (на англ.):
...читать далее "Настройка производительности PgSQL"

11

Я уже публиковал несколько модификаций для некоторых функций из libc, оптимизированных для быстрой работы на современных процессорах (см. категорию Algorithms and Technologies).

Все эти функции были реализованы в поисковом движке DataparkSearch Engine. Поскольку производительность этих функций, особенно в сравнении со стандартной реализацией на конкретной платформе, зависит от используемых микропроцессора и уровня оптимизации компилятора, я добавил специальную процедуру тестирования на этапе конфигурирования DataparkSearch, выбирающую только те новые варианты функций, которые исполняются быстрее на платформе, где производится установка. Это позволяет получить максимальную производительность DataparkSearch на каждой платформе.
...читать далее "Небольшое ускорение"

8

Рейтинг персон Сочи обновлен с учетом морфологии некоторых фамилий и редких имён. Для этого к словарю русского языка для ispell от Александра Лебедева были сделаны следующие дополнения:
...читать далее "Морфология фамилий"

3

Быстро, какой самый быстрый способ поиска в упорядоченном массиве?

Двоичный поиск, правильно?

Неправильно. На самом деле существует метод, называемый интерполяционным поиском, в котором вместо банального выбора середины массива, используется модель распределения ключей для предсказания места нахождения искомого ключа и проверки его.
...читать далее "Обставляя двоичный поиск"

Создал на Mendeley коллекцию RuSSIR, присоединяйтесь.
...читать далее "Коллекция RuSSIR"

5

В еще более быстрой версии функции strncpy был существенный недостаток, - она не полностью соответствовала спецификации, а именно, не дополняла нулями, если строка-источник оказывалась короче указанной длины. Вариант ниже исправляет этот недостаток, но по-прежнему быстрее стандартной функции будучи скомпилированным с включенной оптимизацией кода для современных процессоров:
...читать далее "Исправленная быстрая strncpy"