MikhailEdoshin

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

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

Восемь символов каждый по пять бит дают 40 бит информации, то есть 1,099,511,627,776 номеров. Для миллиарда номеров достаточно 30 бит (2^30 = 1,073,741,824). Оставшиеся десять бит (которые, естественно, могут идти не по порядку) можно заполнить случайной информацией и/или использовать для контрольной суммы, дополнительных пометок (номер серии) и т. п. Разумеется, если у вас будут более длинные номера, то простора еще больше.

Один из приемов генерации непоследовательных уникальных номеров — взять последовательный номер и применить к нему маскирующую операцию, например, инвертировать заданные биты, а затем переставить по фиксированной схеме. Пусть у нас будут трехбитные номера от 0 до 7: 000, 001, 010, 011, 100, 101, 110, 111. Сначала инвертируем второй бит: 010, 011, 000, 001, 110, 111, 100, 101. Получаются все те же номера, но уже в другом порядке — 2, 3, 0, 1, 6, 7, 4, 5. Затем, считая что биты нумеруются 321, переставим их в 132: 001, 101, 000, 100, 011, 111, 010, 110 — 1, 5, 0, 4, 3, 7, 2, 6.

Может быть, имеет смысл также добавить контрольную сумму, пусть хоть бит четности — 0010, 1010, 0001, 1001, 0110, 1110, 0101, 1101 или 2, 10, 1, 9, 6, 14, 5, 13. Числа остаются уникальными, и полностью обратимыми, но расползаются по большему диапазону.

Учитывая, что чисел мало, проще хранить их в отсортированном массиве — 5 млн 32-битовых чисел займут 19 МБ, пересечение и разность находятся так же параллельным просмотром за O(N + M), проверка вхождения элемента двоичным поиском — O(log N).

Нет. Как вы себе представляете работу такой функции? А если дом 122? Или 21? Тоже одинаковый хэш должен быть? А если улица «Масюковская» — тоже? А когда он должен делаться неодинаковый?

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

По-моему, что-то похожее описано у Кнута в книге «Все про Metafont» (в третьей главе). Вообще там используются кривые Безье, но оператор задает непосредственно только крайние точки, через которые кривая будет на самом деле проходить, а вспомогательные точки алгоритм рассчитывает сам.

См. также StackOverflow.

Сливать отсортированные массивы удобно с помощью кучи. Пусть n — общее число элементов и k — количество массивов. Делаем кучу из k элементов, укладываем в нее первые элементы массивов. Затем на каждом шаге извлекаем из нее минимальный элемент (log k) и добавляем обратно тот, который следует за ним в массиве (log k). Общая сложность этого шага — 2n log k.

Так руками ж в фотошопе пять минут. Берете кусок текстуры, делаете ей filter — offset на половину ширины и высоты, получаете швы по центру. Вооружаетесь штампом и замалевываете швы (осторожнее с краями). Еще раз offset, проверяете как получилось. Определяете паттерн и пользуетесь.

Да, конечно. А то есть, скажем, libfa, но не хватает знания теории, чтобы ею пользоваться.

Ну если перевести вводный абзац отсюда это хеширование, где значения распределяются по «корзинам» (buckets) не равномерно, как это обычно делается при хешировании, а чаще с одной стороны, чем с другой. Когда количество элементов по отношению к числу корзин достигает некоторого порога, число корзин, как и в других алгоритмах, увеличивается, но разбивается только одна корзина — первая с той стороны, где гуще. Предполагается, что это самая полная корзина.

Как мне кажется, можно попробовать следующее. Когда три круга с радиусами a, b, c касаются, их радиусы образуют треугольник со сторонами a+b, b+c и с+a. (Радиусы касающихся кругов лежат на одной прямой, отсюда один шаг до треугольника.)

Зная стороны треугольника, можем вычислить его углы. Вычислим для начала угол в центре a. Возьмем следующий круг d и приставим его к a и c. Образуется еще один треугольник из кругов a, c и d. Мы опять-таки можем вычислить его угол. Очевидно, мы можем таким образом укладывать круги вокруг a до тех пор, пока сумма внутренних углов не превысит 360 градусов.


После этого мы можем начать укладывать оставшиеся круги вокруг b. У него к этому времени уже будет занята часть круга — кругами a, c и, возможно, последним кругом, уложенным с другой стороны a.

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

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

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

О, моя любимая задача. Есть такое UB-Tree (плюс в Википедии ссылки полезные) из того же материала от того же Рудольфа Бауэра, что изобрел и B-Tree. На мой взгляд, правда, слишком оно головоломное, и сам я его не испытывал.

Насчет подструктуры ничего сказать не могу, но это упрощенный алгоритм Кнута-Пласса о выключке абзаца, соответственно направление мысли — посмотреть их работу :) Из вики:

Formally, the algorithm defines a value called badness associated with each possible line break; the badness is increased if the spaces on the line must stretch or shrink too much to make the line the correct width. Penalties are added if a breakpoint is particularly undesirable: for example, if a word must be hyphenated, if two lines in a row are hyphenated, or if a very loose line is immediately followed by a very tight line. The algorithm will then find the breakpoints that will minimize the sum of squares of the badness (including penalties) of the resulting lines. If the paragraph contains n possible breakpoints, the number of situations that must be evaluated naively is 2n. However, by using the method of dynamic programming, the complexity of the algorithm can be brought down to O(n2) (see Big O notation). Further simplifications (for example, not testing extremely unlikely breakpoints such as a hyphenation in the first word of a paragraph) lead to an efficient algorithm whose running time is almost always of order n. A similar algorithm is used to determine the best way to break paragraphs across two pages, in order to avoid widows or orphans (lines that appear alone on a page while the rest of the paragraph is on the following or preceding page). However, in general, a thesis by Michael Plass shows how the page breaking problem can be NP-complete because of the added complication of placing figures.[18]

По-моему, единственный вариант с ожидаемым O(1) — хэш-таблица. Если данные известны, можно подобрать perfect hash function и тогда O(1) будет гарантирован.

А многочисленные вариации CRC почему не годятся?

Если язык позволяет (C, например), можно несколько ускорить нахождение второго числа после того, как найдено первое, задав для поиска меньший интервал.

Хотя на современных шибко умных процессорах это не обязательно будет быстрее.