Способ многопоточного сравнения значений двух массивов. Java?
Есть два массива со строковыми данными. Первый массив может содержать мало значений (4-5) , а может достаточно много (500-1000) , второй массив содержит фиксированное число строк , например (20). Какой алгоритм оптимален для сравнения каждого элемента первого массива со всеми элементами второго массива ?
Сравнение должно происходить как можно быстрее, например банальный вариант взять и сравнить каждый элемент со всем вторым массивом можно считать долгим.
Не нужен код , нужна идея как это реализовать.
каждое строка из первого массива (слово) сравнивается со вторым массивом ровно до первого совпадения.
Длинна строки первого массива зависит от того насколько большое слово можно написать не используя пробел, во втором массиве строки будут небольшого размера от 4 до 10 символов.
В первом массиве может быть сколько угодно одинаковых строк ( хоть весь массив)
во втором массиве одинаковые строки исключены.
Данные в первом массиве это какой либо текст , во втором массиве ключевые слова.
Если у Вас заранее известное и небольшое кол-во строк во втором массиве, то создайте хеш-таблицу из второго массива размера, гарантирующего отсутствие коллизий между строками второго массива и сразу же в хеш-таблице укажите индекс возможно совпавшей строки по второму массиву.
В итоге:
- предзатраты = расчет хешей строк второго массива (заполнение таблицы),
- затраты сравнения = расчет хеша строки первого массива + 1 операция выборки из массива + если есть подозрение на совпадение - полное сравнение строки.
Попробуйте в начале посчитать "хэш" для каждого ключевого слова а затем последовательно считать "хэши" для текста и сравнивать с ключевыми.
Собственно, мопед не мой. Подход реализован в известном алгоритме Рабина-Карпа
да я уже решил что проще будет по простому сравнить так второй массив реально мал , а время на прогон большой статьи (3000 слов) не более 100 милисекунд, при этом для второго массива я даже не пользуюсь базой данных , все читается из текстового файла, так что если я буду считать хеш то придется делать синглтоновский класс ( я делаю сервелатами все это)
Простой