Wataru

Ваш алгоритм быстрее. Но в задаче часто бывает сработает не только самый быстрый код. Например, если там чисел всего 10 в массиве, то вы никакими измерениями разницу между сортировкой и вашим решением не намеряете (если только не запустите оба решения миллионы раз. Но это же уже другая задача. Ваша задача - найти минимальные 2 числа в одном массиве и ограничение по времени, если и есть, будет считаться по одному массиву)

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

В вашем алгоритме еще проблема, что не очевидно, почему он работает. Надо аккуратно рассматреть все 6 случев расположения arr[0], arr[1] и numbers[i] и убедиться, что инваринат "2 минмальных числа лежат в arr" поддерживается. Тут легко накосячить, перепутать 0 и 1, не там проверку поставить и все.

Обычно, когда такой алгортм реализуют, поддерживают более строгий инвариант "минимальное число в arr[0], следующее минимальное число в arr[1]". Тогда проверки чуть чуть упрощаются и за логикой решения следить проще.

Вам уже подсказали: Триангуляция по 4 точкам.

При чем не надо решать систему в общем виде. Если вы возьмете ваши 4 точки как (0,0,0) и (0,0,1), (0,1,0) и (1, 0, 0) то вы уже можете найти координаты искомой точки, не решая даже квадратных уравнений или систем.

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

x^2+y^2+z^2 = d1^2
x^2+y^2+(z-1)^2 = d2^2

Вычтите одно уравнение из другого, сократите все сокращаемое, поделите на 2 и в одно арифмитическое действие найдете z.

Точно также можно найти x и y, рассматривая другие пары уравнений.

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

Так, вашу задачу можно переформулировать в виде максимального потока минимальной стоимости из нескольких разных жидкостей (исток k-ой жидкости в точке k, сток - в k+1. Чтобы вершины нельзя было переиспользовать их надо раздвоить на входную и выходную, соедененные ребром).

Похоже, что в вашей задаче может хорошо работать метод отжига, или генетический алгоритм.

Я сомневаюсь, что даже для графа-сетки есть какой-то более простой алгоритм.

Раз уж я в комментариях все разобрал, скопирую в ответ: куча мелких ошибок в коде, вроде:
- циклы с 1 вместо 0
- не инициализированные массивы
- опечатки

А вы можете сами логику своего решения сформулировать? Какой инвариант поддерживается при запуске рекурсивной функции?

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

Но ваш подход со swap-ами первого не зафиксированного числа со всеми остальными перемешивает эти оставшиеся числа. Если вы пройдетесь по вашему решению отладчиком или будете выводить arr в начале функции всегда, то вы заметите, что там числа после index идут не по порядку. И ваш алгоритм, беря их индесы по порядку, может сначала поробовать не самое маленькое число.

Вам надо добиться того, что оставшиеся в arr числа после index всегда шли по порядку на момент рекурсивного вызова.

Пусть ставшиеся числа 1,2,3,4. Сначала вы ставите на первую позицию 1 (оставляете все как есть).
Потом вы должны получить в массиве 2,1,3,4 и запуститься рекурсивно. Это один swap.
Потом надо получить в массиве 3,1,2,4. Это можно сделать одним swap из предыдущего состояния.
Важно тут, что вы не возвращаете массив назад после каждого рекурсивного вызова. Иначе вам пришлось бы делать циклический сдвиг части массива на каждой итерации (1,2,3,4 -> 3,1,2,4).

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

Т.е. рекурсивные вызовы будут как-то так:

perm( arr, size, index + 1 );
for( i = index + 1; i < size; i++ )
{
    swap( arr[i], arr[index] );
    perm( arr, size, index + 1 );
}
int tmp = arr[index];
for (i = index; i < size-1; i++)
    arr[i] = arr[i+1];
arr[size-1] = tmp;

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

Один вариант относительно быстрого поиска одинаковых подстрок - это суффиксные деревья. Придется много поломать голову, как хранить эффективно 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 сдвинутся так, что длина отрезка уменьшится. Алгоритм не циклится.