Предложения, необходимые для оптимизации алгоритма O (n ^ 2)

Question

Я хочу оптимизировать довольно простой алгоритм, который в настоящее время O (n ² ) .У меня есть файл записей, где каждый из них должен сравниваться друг с другом в одном файле.Если они одинаковы (функция сравнения довольно сложная), соответствующие записи выводятся.Обратите внимание, что может быть несколько записей, совпадающих друг с другом, , и отсутствует порядок следования - только если совпадение истинно или неверно.

Псевдокод:

For (outRec in sourceFile) {
  Get new filePointer for targetFile //starting from the top of the file for inner loop
  For (inRec in targetFile) {
    if (compare(outRec, inRec) == TRUE ) {
      write outRec
      write inRec
    }
    increment some counters
  }
  increment some other counters
}

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

Любые идеи о том, как это может стать чем-то меньшим, чем O (п ² ) ?Я подумываю применить парадигму MapReduce к коду, разбить внешние и внутренние циклы, возможно используя цепную функцию Map.Я почти уверен, что у меня есть код, разработанный для Hadoop, но хотел проверить альтернативы, прежде чем потратить время на его кодирование.

Предложения приветствуются!

Добавлено: Типы записей.По сути, мне нужно сопоставить имена / строки.Типы соответствия показаны в примере ниже.

1,Joe Smith,Daniel Foster<br>
2,Nate Johnson,Drew Logan<br>
3,Nate Johnson, Jack Crank<br>
4,Joey Smyth,Daniel Jack Foster<br>
5,Joe Morgan Smith,Daniel Foster<br>
<br>
Expected output:
Records 1,4,5 form a match set
End of output

Добавлено: эти файлы будут довольно большими.Ожидается, что самый большой файл будет около 200 миллионов записей.

Answer 1

Я не уверен насчет свойств вашего компаратора и набора данных, но при условии, что ваш компаратор определяет отношение эквивалентности для ваших строк, здесь ничего не говорится:

1. Создайте карту для входного файла и используйте функцию компаратора в качестве ключевого компаратора карты. Значения карты представляют собой последовательность / список строк, то есть все «одинаковые» строки последовательно добавляются к одной и той же записи карты). Занимает O (n * log n) время.
2. Пройдите по строкам другого файла и проверьте, соответствует ли каждая строка ключу на карте. В этом случае из-за отношения эквивалентности, подразумеваемого вашим компаратором, вы знаете, что эта строка «совпадает» со всеми строками в значении этой записи карты. Принимает O (n * log n + C), в зависимости от того, сколько совпадений вы должны вывести.

Обратите внимание, что в худшем случае, согласно описанию вашей проблемы, вы не можете получить ничего лучше, чем O (n ^ 2), просто потому, что может быть O (n ^ 2) результатов сопоставления записей, которые вы должны вывести!

Answer 2

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

Чтобы улучшить время на настенных часах, первое, что нужно сделать, - это найти способы избежать необходимости проводить сравнение. Любой способ сделать это будет победой. И даже если ваша логика сравнения сложна, вы все равно можете использовать сортировку, чтобы помочь.

Например, предположим, что у вас есть какое-то измерение, в котором эти данные распределены. Данные, которые слишком сильно различаются в этом измерении, гарантированно не будут сравниваться, хотя близость в этом измерении не гарантирует равенства. Тогда вы можете отсортировать данные по этому измерению, а затем выполнить сравнение только между элементами, близкими в этом измерении. Вуаля! Большинство O(n*n) сравнений теперь пропало.

Давайте сделаем это более сложным. Предположим, вы можете определить два таких измерения, которые не зависят друг от друга. Сортируйте ваши данные по первым таким измерениям. Разделите данные в первом измерении на полосы. (Сделайте так, чтобы полосы перекрывались по максимуму, который они могут варьировать в этом измерении, и при этом сравнивайте их равными.) Теперь возьмите каждую полосу и отсортируйте ее по второму измерению. Затем выполните сравнения между парами элементов, которые являются приемлемо близкими в этом измерении, и включите эту пару в свой ответ, если он сравнивается равным, и это первая полоса, в которой он может появиться. (Эта логика дедупликации необходима, потому что перекрытие может означать, что пара, которая сравнивает равные, может появиться в нескольких полосах.) Вероятно, это будет даже лучше, чем в первом подходе, потому что вам удалось сузить все, чтобы сравнивать только строки с небольшим количеством «соседних» строк.

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

Answer 3

Нам нужно больше узнать о вашей функции сравнения. Ваше сравнение транзитивно? (То есть A == B и B == C означают A == C?) Это рефлексивно? (А == B подразумевает B == A?)

Если ваша функция сравнения транзитивна и рефлексивна, а многие равные записи являются общими, то вы можете объединить свои записи в группы, сравнив их с одной «репрезентативной выборкой» группы. Это может приблизиться к O (N) в лучшем случае.

Обратите внимание, что при хешировании записей предполагается, что hash (A) == hash (B) <=> сравнить (A, B) == true, но если сравнение (A, B) может быть истинным, даже если байты (A)! = bytes (B) может быть сложно разработать подходящий алгоритм хеширования.

Answer 4

Предполагая, что файлы не слишком большие, я бы просмотрел файл целиком, вычислил хеш для строки и отслеживал комбинации хэш / строка # (или положение указателя файла). Затем отсортируйте список хэшей и определите те, которые появляются более одного раза.

Answer 5

Как вы уже упоминали, вам не повезет, что он будет лучше, чем O (n ^ 2), но вы можете это парализовать.

У меня есть рабочее решение, которое будет работать с HDFS, вы можете расширить его с помощью распределенного кэша.

public class MatchImporter extends Mapper<LongWritable, Text, Text, Text> {

FileSystem fs;
private BufferedReader stream;

@Override
protected void setup(Context context) throws IOException,
        InterruptedException {
    fs = FileSystem.get(context.getConfiguration());
}

private void resetFile() throws IOException {
    if (stream != null)
        stream.close();
    stream = new BufferedReader(new InputStreamReader(fs.open(new Path(
            "files/imp/in/target.txt"))));
}

private boolean compare(Text in, String target) {
    return target.contains(in.toString());
}

enum Counter {
    PROGRESS
}

@Override
protected void map(LongWritable key, Text value, Context context)
        throws IOException, InterruptedException {

    resetFile();
    String line = null;
    while ((line = stream.readLine()) != null) {
        // increment a counter to don't let the task die
        context.getCounter(Counter.PROGRESS).increment(1);
        context.progress();
        if (compare(value, line)) {
            context.write(new Text(line), value);
        }
    }
}

public static void main(String[] args) throws Exception {
    Configuration conf = new Configuration();
    Job job = new Job(conf);

    job.setMapperClass(MatchImporter.class);
    job.setReducerClass(Reducer.class);
    job.setJarByClass(MatchImporter.class);

    Path in = new Path("files/imp/in/source.txt");
    Path out = new Path("files/imp/out/");

    FileInputFormat.addInputPath(job, in);
    FileSystem fs = FileSystem.get(conf);
    if (fs.exists(out))
        fs.delete(out, true);

    SequenceFileOutputFormat.setOutputPath(job, out);
    job.setInputFormatClass(TextInputFormat.class);
    job.setOutputFormatClass(TextOutputFormat.class);
    job.setOutputKeyClass(Text.class);
    job.setOutputValueClass(Text.class);

    job.waitForCompletion(true);
}

}

Использование ввода в source.txt:

thomas
phil
jen
james
christian
stefan
stephan
john

и target.txt

john meat
jay hardly

приведет к выходу редуктора:

john meat   john

Хитрость в том, что вы можете разделить ваш source.txt и выполнять сравнение параллельно. Это даст вам ускорение, но не поможет вам в больших O.

Одна большая заметка здесь: Вы должны сообщать о прогрессе, используя счетчик, потому что сравнение с целым файлом может длиться вечно. Это предотвратит сбой вашей задачи в распределенной среде.

Маленький совет: Попробуйте разделить ваш source.txt на 64 млн кусков и сделать target.txt равным sequencefile. Это значительно ускорится, тогда вам придется переписывать читаемые материалы.

Желаю вам удачи!

Answer 6

Просто просмотрите каждую запись вашего файла и вставьте их в хеш-таблицу. На каждом шаге проверяйте, есть ли запись в хеш-таблице. Если это так, выведите его. Это можно сделать за O (n).

Answer 7

Как отмечает btilly, вам на самом деле не нужна транзитивность для классификации записей. В случае имен англичан вы можете представлять каждое имя двумя инициалами, а каждую запись - отсортированным списком инициалов. Тогда вам нужно только выполнить полное сравнение O (N ^ 2) между записями в одном классе. Существует дополнительная проблема, заключающаяся в том, что одна и та же пара записей может появляться в нескольких классах, но ее легко обнаружить, если вести отдельный набор сопоставленных пар записей (идентифицируемых индексами записей).

В этом примере вы поместили бы запись 1 в классе "DF, JS", запись 2 в классе "DL, NJ", запись 3 в классе "JC, NJ", запись 4 в классе "DJ, JS" , "JF, JS" и "DF, JS" и запись 5 в классах "DF, JM", "DF, JS" и "DF, MS". Всего вы получаете 7 классов: «DF, JM», «DF, MS», «DF, JS», «DJ, JS», «DL, NJ», «JC, NJ», «JF, JS», из которых только класс "DF, JS" содержит несколько записей, а именно записи 1, 4 и 5. Таким образом, в этом примере вам нужно всего лишь дважды запустить функцию полного сравнения.

С другой стороны, проблема в том, что у людей странные имена. Эту запись в блоге на эту тему стоит посмотреть, если вы ее раньше не видели. Что бы вы ни делали, некоторые матчи вы пропустите.

Answer 8

Благодаря всем замечательным предложениям.
После прохождения опций, кажется, что лучший подход, учитывая мою временную шкалу, состоит в том, чтобы использовать инфраструктуру MapReduce для распараллеливания проблемы и использования большего количества оборудования.Я понимаю, что это не уменьшает сложность O (n ² ).
Единственное возможное решение, которое я могу придумать, - это запустить какой-нибудь тип minHash для данных, разбить данные на перекрывающиеся секции,и сравнить в полосах и перекрытиях.Это должно уменьшить количество сравнений, но я не уверен, насколько дорогой будет хэширование.

Answer 9

Если вы действительно не можете сделать ничего лучше, чем непрозрачное отношение эквивалентности, тогда ваш худший случай всегда будет O (n ^ 2) - например, для случая, когда нет совпадений,вам нужно будет сравнить каждую пару, чтобы убедиться в этом.(как уже упоминалось, вы можете распараллелить это, но это все равно не будет особенно пригодным для сотен миллионов записей; это может не стоить затрат ресурсов, необходимых для этого).

Обычно, однако, есть какой-то лучший способ сделать это.

Если у вас действительно есть отношение эквивалентности (то есть, если у вас есть логическая гарантия, что если match (a, b) = match (b), c) = true, тогда совпадение (a, c) также верно), возможно, существует некоторая каноническая форма , в которую вы можете преобразовать свои записи, которая поддается хешированию и / или упорядочению.

В вашем примере вы, похоже, подходите по вариантам "Джо Смита".Если это так, вы, вероятно, можете расширить критерии сравнения, чтобы выбрать одного конкретного члена класса эквивалентности для представления целого.Например, выберите «JOSEPH» для представления всех имен, эквивалентных «Joe», «SMITH» для представления всех имен, эквивалентных «Smythe» и т. Д.

После того, как вы выполните это преобразование, вы можете использовать хеш-таблицу дляуменьшите вашу операцию до O (n), а не O (n ^ 2).

Answer 10

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

Если вы просто сортируете входные данные и запускаете функцию сравнения для соседних записей, вы можете отбросить достаточно дубликатов, чтобы выдержать n ^ 2-секундный проход.