Записи с меткой "алгоритмы"

А давайте поиграем в задачки.

Дано: посты с комментариями. У постов есть теги, у комментариев есть авторы. Ну, комментарии и их авторы нас пока не интересуют. Лежит это всё дело в СУБД.

Задача: находить все посты, помечены одним или более тегами (теги на вход подаёт юзер). Чтобы распределение данных было близко к реальности, надо чтобы постов было более 100 тысяч, а количество тегов не превышало 2-3 тысячи, в идеале — +/- 1 тысяча. На пост от 0 до 10-15 тегов (техническое ограничение должно отсутствовать, возможность не указывать теги должна присутствовать).

Ответ СУБД должна выдавать за минимально возможное время. Например, на системе без нагрузки после компиляций планов/поднятия кеша с винта — не более 50 мс на один поиск на стандартном десктопе (примерно i7 860 @ 2.8 GHz, 8 Gb DDR3).

Во время решения задачи можно предполагать, что все данные находятся в оперативной памяти.

Для решения задачи можно использовать любую СУБД, обладающую следующими свойствами:
1. СУБД обязана иметь ACID-транзакции.
2. СУБД обязана уметь гарантировать ссылочную целостность данных. Например, через foreign keys.

ЗЫ: я задачку решил и оно используется у нас в продакшене :)

ЗЫ2: важное забыл. Распределение тегов по постам крайне неравномерно. Может быть так, что одним тегом покрыто 10% постов, а другим — 2 (два, не два процента) поста. И находить должно с одинаковой скоростью по каждому из таких тегов в отдельности и по обоим вместе.

ЗЫ3: решение задачи — это минимум два запроса: тот, который создаст структуру базы и тот, которым вы выберите посты (id, text минимум) по заданному вводу.

8
Окт

intellegent design sorting

   Автор: Aen Sidhe    в программирование

The probability of the original input list being in the exact order it’s in is 1/(n!). There is such a small likelihood of this that it’s clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it’s safe to assume that it’s already optimally Sorted in some way that transcends our naive mortal understanding of «ascending order». Any attempt to change that order to conform to our own preconceptions would actually make it less sorted.

(c) не я.