Только одна проблема - ваше решение для сколько-нибудь длинных строк будет работать очень медленно. Удалять скобки по одной паре слишком долго. Плюс еще накладные расходы от регекспов.
Там используется currentTimeMillis (line 268) и много повторений. Для академического сравнения алгоритмов, как у автора вопроса, тащить этого монстра смысла нет.
Сергей Горностаев, Любая функция измерения времени будет давать какую-то погрешность. Только повторами можно ее сделать сколь угодно малой. Во-вторых, очень точные методы, вроде аппаратных счетчиков, из джавы, по-моему, вообще не доступны, да и смысла в них для бенчмарка нет ни какого. Потому что даже если вы количество тактов процессора (куда уж точнее) мерять будете, у вас все-равно разброс будет. Время выполнения - это случайная величина, потому что зависит от миллиона разных факторов: что и как было в кэше, что операционка решила делать во время ваших тестов, какие были прерывания, да, в конце концов, как тепло распределилось в процессоре и памяти.
Поэтому гонять один и тот же код на одних и тех же данных много-много раз просто необходимо. Точность функции измерения времени в этих условиях отходит на второй план. Хотите точнее - повторите больше раз.
Если один прогон занимает много времени, то повторите его 100 раз. Если лень ждать - 10 раз. Если данных много и один прогон - несколько секунд, то наносекундами точности можно принебречь. Если один прогон занимает микросекунды, то повторить его миллионы раз - не проблема.
Повторять и брать среднее в любом случае придется - чтобы избавится от случайностей и погрешностей. Один и тот же код на одних и тех же данных может выполнятся, например, от 10 до 20 миллисекунд.
"Нужно генерировать по опорным признакам соответствия заданной строки к искомой." Что за опорные признаки? Не понял ваше предложение совсем. Что такое "целочисленный наборный полином"? У вас есть ссылки или английский термин? Я ничего по этим ключевым словам нагуглить не смог.
Как вы поставили задачу - получить одно число (или набор признаков) одинаковое для строк с дистанцией редактирования <=2 и разное иначе - невозможно. Из первой части вытекает, что все строки должны давать одинаковые значния и вторая часть задачи (разное для разных строк) противоречит этому.
Можно сильно сэкономить по времени и памяти, используя meet-in-the-middle подход. Надо допускать в каждой строке по 1 ошибке максимум и искать пересечения получившихся множеств.
Можно сделать что-то эвристическое. Например, написать функцию сравнения двух строк. В ней, в зависимости от длин строк, можно понять из какой строки надо удалять символы. Перебрать их позиции, потом проверить, что в получившихся строках не более оствшегося количества несовподений. Эвристика тут в том, чтобы сравнивать только строки, имеющие шанс совпасть с двумя ошибками. Для этого каждую строку надо разбить на 3 равные части. Тогда у двух строк с двумя ошибками обязательно совпадет хотя бы одна из трех частей. Для каждой части, используя сортировку, разбивейте все строки на группы, где совпадает данная часть. Потом проверьте каждую пару с каждой функцией сравнения.
Не понимаю проблемы вообще. Чем плох ранд? Почему нельзя строить массив? функция один раз строит массив, а потом возвращает значение из соответствующей ячейки (номер запроса по модулю 100).
Тогда в начале в цикле for найдите бинпоиском в массиве в позициях 0..i-1 наибольший элемент, меньший array[i]. Пусть эта позиция j. Потом, все там же внутри цикла for циклом while (почти как сейчас) сдвиньте все элементы правее j на одну позицию вправо. Т.е. цикл будет while (index > j+1). Дальше все остается точно так же и внутри цикла while и после. Важно, чтобы ваша реализация бинарного поиска возвращала -1, если все элементы array[0..i-1] больше равны array[i]. Как будто-бы в -1 позиции в массиве стоит бесконечно маленькое число.
