Добрый вечер.
Есть такая задача, которую нужно решить именно на Джаве.
Дано: 1.000.000 строк.
Каждая строка - последовательность символов [a..z] (латинский алфавит в нижнем регистре)
Длина строки - [4..20]
Задача:
Найти все уникальные строки длиной 4 символа.
Уникальная строка не встречается виде подстроки в исходном наборе строк (1.000.000 штук)
Если в уникальной строке заменить один из символов на любой другой, то получившаяся строка так же не должна быть подстрокой исходного набора.
Примеры:
abcd
bbcd
aabbccdd
Среди трех строк нет уникальных, т.к. b
bcd можно получить из a
bcdесли в
bbcd сделать одну разрешенную замену (
bbcc), то новая строка будет найдена внутри строки aa
bbccdd
Если в исходный набор добавить строку
aaaa,
то она и будет уникальной, т. к. при любой одной замене она не будет подстрокой трех первых строк.
Обратная связь: из первых двух четырехсимвольников нельзя получить строку aaaa.
Задача имеет временные рамки (не более 4 мин) и ограничения по оперативной памяти (не более 128 мегабайт).
Моё решение (прошу оценить, раскритиковать):
При помощи BufferedReader (метод readLine) начитывать исходные строки.
Для входящих строк есть три списка:
1. Список(ArrayList<String>) строк, длина которых >4 символов.
2. Список 4ех символьных строк - "кандидатов на уникальнось"
3. Список 4ех символьных строк, которые не уникальны.
Алгоритм нарисован на картинке.
В отведенное время и объем памяти укладываюсь. Сделал на ArrayList и на FastList (javolution.org).
Для сравнения строк использую два способа:
1. через регулярку
2. через модули
Допустим, есть две строки:
abcd
abzd
перебираю возможные комбинации:
1,2,3 | 2,3,4 | 1,2,4 | 1,3,4
если разница по модулю символов (char) на указанных позициях == 0, значит строки эквиваленты.
в случае двух строк abcd, abzd разница чаров на позициях 1,2,4 даст "0":
a-a + b-b + d-d = 0
Если надо сравнить 4ех символьную строку и длинную строку, то последовательно из длинной строки выбираю 4 символа и сравниваю их с 4ех символьной строкой.
Такой способ сравнения строк в среднем на 2 порядка быстрее (!), чем через регулярки.
Сейчас работаю над решением через БД SQLite, которая позволяет (если я все правильно понял) избавиться от I/O операций, поместив всю базу (in-memory database) в оперативочку.
RFC.
Хочется знать, насколько я далёк от идеала.
P.S.
Для тестового набора использую генератор строк, рандомно выдающий строки длиной [4..20], сотоящих из символов [a..z].
байт), в котором хранить счётчик вхождения этой (или похожей на неё в смысле задачи) подстроки в исходных данных. Счётчик сделать насыщаемым, т.е. если число вхождений достигло двух, более его не увеличивать (поэтому для него достаточно не байта, а 2-х бит). Алгоритм тривиален: пройтись по всем строкам, увеличивая для каждой 4-символьной подстроки и для всех похожих на неё (ещё 100 штук) счётчик с учётом насыщения. Затем проходимся по массиву счётчиков, ища единицы (насколько я понял, в задаче не требуется для каждой уникальной подстроки указывать, откуда она взялась, иначе надо усложнять структуру). Число операций --- порядка пары миллиардов, наверное, 4-х минут хватит.