jQuery → Плагин jQuery для сортировки таблиц: TableSorter.js. Как добиться постраничной навигации? из песочницы
Вступление
При разработке одного проекта мне пришлось решать проблему с сортировкой данных в таблице. Не хотелось для этого использовать PHP, так как эффект теряется при перезагрузке страницы. Вот и наткнулся я на официальный сайт jQuery-плагина "TableSorter.js" — www.tablesorter.com. Немного покопавшись в англоязычной документации я с радостью обнаружил в новостях сайта ссылку на русскоязычный сайт: www.tablesorter.ru.В принципе там всё предельно ясно было описано и я быстро понял как всё работает…
Но было в документации одно важное упущение: недостаточно описан принцип работы постраничной навигации, да и нужные файлы не выложены. А мне как-раз нужна была эта функция, так как в моих таблицах было минимум по 150 строк. Пришлось самому решить эту проблему.
JavaScript → Массивы JavaScript в различных браузерах
Данный код позволяет определить, в каком из популярных браузеров он исполняется, базируясь на их особенностях работы с массивами:
<script type="text/javascript">
function browser() {
if(-[1,]){
var f = 1; var d={4294967296:'opera', d:'firefox', 4294967295:'chrome', '1' :''};
for(var i in d) if(f) f=0; else return d[i];
} else return 'ie';
}
document.write(browser());
</script>Посмотреть его работу «в живую» можно здесь: ritsuka.ru/share/test.html
Блог компании Инфопульс Украина → Алгоритм сортировки Timsort
Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.
Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.
Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.
Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.
Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.
Алгоритмы → Естественная сортировка строк на JavaScript
Задача сортировки является едва ли не наиболее часто решаемой программистами проблемой. Несмотря на то, что распространённых алгоритмов не так много и все они давно написаны и оптимизированы для любых языков и платформ, в исходниках то и дело мелькают методы SortList() и им подобные. Наверное, каждый из нас не раз писал сортировку пузырьком и удивлялся, почему же она не работает с первого раза.
Однако речь сейчас не об алгоритме сортировки, а о способе сравнения строк. Казалось бы, здесь всё тривиально — достаточно сравнить первые с начала различающиеся символы. А если в строках есть числа? Тогда такая сортировка (лексикографическая) преобразует последовательность [ 'file2', 'file10', 'file1' ] в [ 'file1', 'file10', 'file2' ]. Но человек при чтении текста воспринимает числа отдельно, и эта же последовательность, упорядоченная интуитивно, выглядит так: [ 'file1', 'file2', 'file10' ]. Такая сортировка и называется естественной (natural sort).
Под катом —велосипед подробный алгоритм на JavaScript. На оптимальность и красоту он не претендует, но всё же лучше, чем многопроходная реализация «в лоб».
Однако речь сейчас не об алгоритме сортировки, а о способе сравнения строк. Казалось бы, здесь всё тривиально — достаточно сравнить первые с начала различающиеся символы. А если в строках есть числа? Тогда такая сортировка (лексикографическая) преобразует последовательность [ 'file2', 'file10', 'file1' ] в [ 'file1', 'file10', 'file2' ]. Но человек при чтении текста воспринимает числа отдельно, и эта же последовательность, упорядоченная интуитивно, выглядит так: [ 'file1', 'file2', 'file10' ]. Такая сортировка и называется естественной (natural sort).
Под катом —
PHP → Мгновенный поиск в 75 гигабайтах из песочницы
Речь пойдет о том, как был реализован быстрый поиск по большим объемам данных на этой страничке. Там можно искать пароль по хешу, для игрового сервера PvPGN, и генерировать эти же хеши.
Поиск написан на чистом PHP, без использования модулей и сторонней БД. В принципе, таким образом можно наращивать объемы до многих терабайт, было бы место — скорость от этого не сильно пострадает.
Далее от начала до конца описан весь процесс, который включает в себя брутфорс, создание хеш таблицы, её сортировка и, собственно, поиск.
Поиск написан на чистом PHP, без использования модулей и сторонней БД. В принципе, таким образом можно наращивать объемы до многих терабайт, было бы место — скорость от этого не сильно пострадает.
Далее от начала до конца описан весь процесс, который включает в себя брутфорс, создание хеш таблицы, её сортировка и, собственно, поиск.
Интерфейсы → А бывает ли фонетическая сортировка?
Глядя сегодня в адресную книгу своего телефона на Андроиде, я понял, что мне неудобно смотреть на список моих контактов, отсортированный по порядку символов в UTF.
Алгоритмы → Двоичные таблицы Юнга
Итак, как и обещал, продолжение темы о таблицах Юнга. Напомню, что под таблицей Юнга понимается числовая матрица, обладающая некоторыми специальными свойствами. Матрица – это двумерный массив. И вот тут должен возникнуть естественный вопрос – а почему, собственно, массив должен быть двумерным? А что, если мы попробуем реализовать на тех же принципах таблицу размерности три, или четыре, а лучше всего, конечно, пять звездочек! О том, куда приведет нас такое обобщение, можно прочитать под катом…
Алгоритмы → Таблицы Юнга в задачах поиска и сортировки из песочницы
Таблицы Юнга являются широко известным (в узких кругах) типом объектов, изучаемых в комбинаторике и смежных науках: ссылка, ссылка, книжка. Ниже рассматривается применение частного вида таблиц Юнга применительно к таким стандартным алгоритмическим задачам, как поиск и сортировка. С этой точки зрения таблицы Юнга весьма близки пирамидам, собственно так они и позиционируются в учебнике Кормена и ко (упражнения в разделе, посвященном пирамидам).
Программирование → Трюк с сортировкой или как не писать лишнего
Топик написан сильно начинающим разработчиком в помощь таким же начинающим сэкономить время и всё-такое с помощью одного нехитрого трюка с сортировкой и невидимым столбцом.
Алгоритмы → Сортировка массива за O(N) на CUDA из песочницы
Введение
Как-то стояла задача отсортировать уникальный массив строк с использованием GPU с минимум кода и максимально возможной скоростью…
В данном посте опишу основную идею ее решения. В качестве элементов массива сортировки в данном посте выступают числа.
Случай с уникальными элементами небольшого массива
В качестве платформы была выбрана CUDA по причинам, которые можно считать брэндовыми или индвидуальными. По факту, здесь много примеров именно на CUDA, и она на данный момент получила большее развитие в GPU-вычислениях, чем аналогичные платформы от ATI и OpenCL.
Поиск в сети по алгоритмам сортировки на CUDA дал разные результаты. Вот наиболее интересный. Там есть рисунок
, из которого видно, что наилучший результат дал алгоритм QSORT, который дает сложность порядка от O(NlogN) до O(N^2). И хотя распараллеливание на GPU дало лучший в статье результат, закралось сомнение, что QSORT — не лучший способ использовать ресурсы видеокарты для данной задачи (особенно испугал размер приведенного кода). Далее описывается решение задачи, по сути «в одну строчку» ссложностью временной сложностью O(N) в худшем случае.
Как-то стояла задача отсортировать уникальный массив строк с использованием GPU с минимум кода и максимально возможной скоростью…
В данном посте опишу основную идею ее решения. В качестве элементов массива сортировки в данном посте выступают числа.
Случай с уникальными элементами небольшого массива
В качестве платформы была выбрана CUDA по причинам, которые можно считать брэндовыми или индвидуальными. По факту, здесь много примеров именно на CUDA, и она на данный момент получила большее развитие в GPU-вычислениях, чем аналогичные платформы от ATI и OpenCL.
Поиск в сети по алгоритмам сортировки на CUDA дал разные результаты. Вот наиболее интересный. Там есть рисунок
, из которого видно, что наилучший результат дал алгоритм QSORT, который дает сложность порядка от O(NlogN) до O(N^2). И хотя распараллеливание на GPU дало лучший в статье результат, закралось сомнение, что QSORT — не лучший способ использовать ресурсы видеокарты для данной задачи (особенно испугал размер приведенного кода). Далее описывается решение задачи, по сути «в одну строчку» с