Wataru

Пока главная проблема, что надо сравнивать все строки со всеми. Если бы их поделить на какие-то части, когда сравнивается не так много строк, пусть даже этих частей много, то задача решается Гораздо проще.

Один вариант относительно быстрого поиска одинаковых подстрок - это суффиксные деревья. Придется много поломать голову, как хранить эффективно 256 ссылок на детей так, чтобы дерево не занимало в тысячи раз больше чем вохдная строка, но это возможно. Например, хранить отсортированный список исходящих символов в каждой вершине.

Вот построили вы деревья для всех строк, дальше надо их попарно сравнить простым рекурсивным обходом. Если оба дерева содержат переход по какому-то символу, рукурсивно идите по нему. Если дошли до глубины N - вы нашли совпадение. Можно вообще идти пока не обломитесь и взять максимальную глубину. Такой обход обойдет дерево один раз для каждой пары строк. Да, еще надо будет хорошенько потрахаться с хранением дерева на диске и подгрузкой его кусками, ибо в оперативку оно все не поместится никак.

Второй вариант, возможно более подходящий для таких объемов данных - это полиномиальные хеши. Можно для каждой строки вычислить L-N+1 хешей для всех подстрок длины N. Первый хеш считается тупо по формуле, а дальше дописывание одного символа справа и удаление одного символа слева можно за 2 операции пересчитать. Вот так вы быстро, за линейное время, можете построить все хеши для одной строки. Запишите их в файл, отсортируйте его (гуглите - известная задача сортировки очень большого файла). А потом операцией слияния можно найти повторяющиеся числа во всех файлах.

Более того, можно не сравнивать каждый файл с каждым, а выполнять слияние сразу на всех файлах. Для этого надо завести приоритетную очередь, она же куча, она же heap, в которую складывать текущие числа из всех файлов (по одному из файла) вместе с указателем на сам файл. Вам надо из этой очереди вынуть минимальное число, и потом вынимать дальше, пока минимум в очереди не изменился. Т.е. вынуть все одинаковые минимальные числа. Файлы, на которые они указывают - это строки с совпадениями. Пометьте это где-то, и для каждого файла прочитайте следующее число и положите его в очередь.

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

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

Если все-таки надо искать совпадения по всем строкам глобально, то придется помучиться. Разбейте ваши данные на K частей примерно одинакового размера так, что каждый компьютер может обработать по 2 части, а хранить хотя бы по 3 части.

В идеале у вас должно быть еще и K/2 компьютеров, иначе схема усложняется.

Надо будет провести K-1 раундов. На первом раунде части 1 и 2 лежат на компьютере 1, части 3 и 4 на втором, и т.д. На втором раунде вы храните части 2 и 3 на компе 1, 4 и 5 на компе 2 ... K и 1 на последнем. При переходе между раундами каждый комп отдает одну часть куда-то, и одну откуда-то получает. На третьем и четвертом раунде вы обрабатываете все пары, в которых вторая часть имеет номер на 2 больше первой части (если брать по модулю K). И так далее. На последнем раунде будут обрабатываться пары, где одно число больше другого на (K-1)/2.

Например, для K=4 вы получаете такие пары на компах:

1. (1,2) (3,4)
2. (2,3) (4,1)
3. (1 3) (2 4)

Тут надо порисовать и составить схему так, чтобы поменьше данных перекладывалось. Для некоторых K так красиво не получится, и какие-то компы будут простаивать на каких-то раундах.

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

В коментариях указали, что списки можно переставлять.

Это известная, очень сложная (NP-сложная) задача об упаковке.

Для сотен тысяч входных списков вы оптимальное по количеству кусков в ответе решение не найдете за все время до тепловой смерти вселенной. Всякие аппроксимации, вроде вашего жадного алгоритма, могут найти лишь какое-то хорошее, но не лучшее разбиение. В частности, у вас используется Next-Fit аппроксимация - вы в итоге можете выдать в 2 раза больше кусков в ответе, чем можно было бы. Есть более сложные алгоритмы, которые, например, гарантируют ухудшение максимум в 1.7 раза.

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

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

Будет. Бинарному поиску главное, чтобы числа в массиве не убывали. Даже если там числа больше предыдущего не только на 1.

Гуглите opencv find matching image part.

Если интересно, что там за алгоритм, то там используется свертка через быстрое преобразование фурье.

Еще есть алгоритмы через перцептивные хеши.

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

Если в метод передаются

left = -1, right = phrases.Count

, то их физический смысл: left - последний элемент точно левее искомой позиции (строка там или меньше pref, или начинается с него), а right - последний элемент точно правее искомой позиции (строка там больше pref и не начинается с него).

Это не совсем стандартный инвариант. Обычно считают, что left, это такая позиция, что ответ не может быть левее ее, а right, что ответ не может быть правее.

Но можно и с вашим инвариантом работать. Вам надо соответсвтующим образом менять left и right, чтобы инвариант поддерживался.

Во-первых, если left == right -2, то вы уже знаете ответ - это может быть только left+1. Эти и должно быть условие в while. Правда стоит эту позицию после цикла все-таки проверить. Вдруг все строки в массиве меньше pref.

Далее, подсчитали вы mid, если строка там оказалась меньше pref или c него начинается, то left = mid. Ведь уже следующая позиция может оказаться искомой, а физический смысл left, напоминаю - "точно левее искомой позиции". В противном случае надо делать right = mid+1. Ведь позиция mid вполне может и быть ответом.

Вопрос, а не зациклится ли такой алгоритм? right-left >= 3. Значит mid оказывается строго больше left. Также, поскольку у вас округление вниз, то mid < right-1, а занчит в любом случае либо left либо right сдвинутся так, что длина отрезка уменьшится. Алгоритм не циклится.

Можно завести флаг "менялись ли элементы в цикле". Перед циклом его сбросить, при перестановке двух элементов - установить. А сам внешний цикл можно сделать while.

Заранее определить, сколько будет итераций - очень сложно.

Во-первых, я бы с помощью бора все урлы перенумеровал. Теперь в задаче есть 400,000 ключевых слов, связанных с 10-ю числами.

Далее, В каждой группе по 10 чисел есть 10!/4!/6! = 840 четверок. Всего различных четверок наберется 840*400000 ~= 330,000,000. Это не так много. Для хранения всей этой радости, правда, понадобится ~8 гигабайт памяти, но это подъемно. Потом вам надо среди этих 300 миллионов найти совпадающие. Можно отсортировать (лучше радиксом) или воспользоваться хеш таблицей (правда тут еще больше памяти потребуется).

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

Судя по всему, это число вылезло в результате эксперементов каких-то исследователей. Они просто попробовали кучу разных факторов и нашли что при 1.247 вроде как быстрее в среднем. Формулу по это число потом какой-то шутник придумал. Кроме как в русской википедии (без ссылки на источник) я нигде эту формулу найти не могу.

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

Сначала выделяется массив какого-то размера, например 256. Обычно длина - степень двойки. Потом хеш обрезается до размера таблицы. Если элементов становится слишком много, то происходит перехеширование - размер таблицы увеличивается, и все элементы в нее перезапихиваются.

Но да, если в таблицу запихать много элементов, а потом почти все оттуда удалить, то она будет большая и почти вся пустая.

Edit:

Эта "проблема" никак не решается. Это и не проблема вовсе. Просто хеш-таблицы работают быстрее всяких балансированных деревьев или тупо сортированного массива за счет большего расхода памяти. Это нужно знать и дальше уже решать - что вам больше подходит под вашу конкретную задачу.

Алгоритм простой - рекурсивно генерируйте все разбиения.
Текущий предмет может пойти или в одну из занятых кучек, или в первую пустую, если они есть.
Так, первый предмет обязательно пойдет в первую группу. Второй может пойти в ту же или во вторую. И т.д.
Чтобы не было пустых групп, элемент обязательно кладется в первую пустую, если их осталось столько же, сколько осталось элементов распределить. Ну, и, нельзя создавать новую группу, их уже, сколько надо. Удобнее распологать элементы с конца.
Что-то вроде такого:

def partition(n, k, answer):
    if n == 0 :
      yield answer
    cur_len = len(answer)
    if k-cur_len < n:
        for i in range(cur_len):
            answer[i].append(n)
            yield from partition(n-1, k, answer)
            answer[i].pop()
    if cur_len < k:
        answer.append([n])
        yield from partition(n-1,k, answer)
        answer.pop()

for x in partition(4, 2, []):
    print(x)

Вроде как set_partitions из пакета more-itertools делает именно то, что вам надо, но так-то алгоритм - всего несколько строк.

Этот алгоритм переберет все разбиения без повторов, потому что групировка элементов однозначно задает и порядок групп (группа с 1 - всегда первая. Потом группа с минимальным элементом - вторая и т.д.)

Edit:
Если же вам надо разбить предметы по 1, 2 и т.д. групп сразу же, а не только на фиксированные k групп, то надо чуть поменять условия в коде - надо сделать return в начале, после yield, и можно будет ставить предмет в любую группу или в новую всегда. Параметр k будет не нужен.

O(1), если "var/www/project" фиксированна. Сравнение двух произвольных строк - линейная сложность.

Сложность: простой.

Если вам нужна ассимптотическая временная сложность - то O(n).
Эта сложность меряется в зависимости от размера входных данных. Какие у вас входные данные-то? Строка slug, url.

Эти данные конкатенируются (O(n)) и передаются библиотеке. До 10 раз. Библиотека их парсит, делает dns запрос, открывает сетевое подключение к web серверу, получает данные, парсит ответ. Там тоже есть линейная, видимо, зависимость от длины строки. Ее надо распарсить, записать в сетевой сокет и так далее. Вот получение данных по уже установленному http соединению от длины строки не зависит, поэтому в сложности алгоритма не учавствует.

По-скольку тут все диапазоны одинаковой длины, то можно формулой:

n = (x - 30)/10;

Тут есть проблема, что интервалы идут и после 6 и еще и в отрицательную сторону.

Можно навесить на это сверху min/max так:

min(6, max(1, n));

Min и max реализуются без if - это известная задача, гуглите.

Edit: Сначала не опнял вопрос, думал надо по заданию без if написать это.

Все-равно, самый быстрый и простой код будет с формулой выше. Только можно проверить на принадлежность крайним интервалом через if:

if (x <= 49) return 1;
if (x >= 90) return 6;
return (x-50)/10 + 2;