2016-08-11 2 views
5

Мне нужно найти пробелы в большом наборе Integer, заполненном циклом чтения через файлы, и я хочу знать, существует ли что-то уже сделанное для этой цели, чтобы избежать простого объекта Set с переполнением кучи ,Лучшая структура данных большого набора в Java

Чтобы лучше объяснить мой вопрос, я должен рассказать вам, как работает мое программное обеспечение для продажи билетов. Каждый билет имеет глобальное прогрессивное число, хранящееся в ежедневном файле журнала с другой информацией. Я должен написать процедуру проверки, чтобы проверить, есть ли пробелы в номерах в ежедневных файлах журнала.

Первая идея состояла в том, чтобы создать цикл чтения со всеми файлами журнала, прочитать каждую строку, получить номер билета и сохранить его в объекте Integer TreeSet, а затем найти пробелы в этом наборе. Проблема в том, что номер билета может быть очень высоким и может насыщать пространство кучи памяти, и я хочу также хорошее решение, если мне нужно переключиться на объекты Long. Решение Set отнимает много памяти, потому что, если я нахожу, что нет пробелов в первом номере 100, нет смысла хранить их в наборе.

Как я могу решить? Могу ли я использовать некоторую структуру данных, уже сделанную для этой цели?

+0

Похоже, что вы можете использовать «BitSet». –

+0

У него нет той же проблемы с памятью набора? – Tobia

+0

все еще линейно по количеству элементов, но каждый элемент занимает всего один бит, а не как минимум 16 (я считаю, что это минимальный размер объекта Java). –

ответ

3

Я предполагаю, что (A) недостатки, которые вы ищете, являются исключением, а не правилом, и (B) файлы журнала, которые вы обрабатываете, в основном сортируются по номеру билета (хотя некоторые записи вне последовательности ОК).

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

В основном, он реализует Set, но фактически сохраняет его как Map, причем каждая запись представляет диапазон смежных значений в наборе.

Метод add переопределяется для обеспечения поддержки Map соответствующим образом. Например, если вы добавите 5 в набор и уже имеете диапазон, содержащий 4, то он просто расширяет этот диапазон вместо добавления новой записи.

Обратите внимание, что причина предположения «в основном отсортирована» заключается в том, что для полностью несортированных данных этот подход будет по-прежнему использовать большую память: карта поддержки будет увеличиваться (поскольку несортированные записи будут добавляться по всему месту) до того, как они станут меньше (поскольку дополнительные записи заполняют пробелы, позволяя объединить смежные записи).

Вот код:

package com.matt.tester; 

import java.util.Collection; 
import java.util.Comparator; 
import java.util.Iterator; 
import java.util.Map; 
import java.util.SortedSet; 
import java.util.TreeMap; 



public class SE { 


    public class RangeSet<T extends Long> implements SortedSet<T> { 

     private final TreeMap<T, T> backingMap = new TreeMap<T,T>(); 

     @Override 
     public int size() { 
      // TODO Auto-generated method stub 
      return 0; 
     } 

     @Override 
     public boolean isEmpty() { 
      // TODO Auto-generated method stub 
      return false; 
     } 

     @Override 
     public boolean contains(Object o) { 
      if (! (o instanceof Number)) { 
       throw new IllegalArgumentException(); 
      } 
      T n = (T) o; 
      // Find the greatest backingSet entry less than n 
      Map.Entry<T,T> floorEntry = backingMap.floorEntry(n); 
      if (floorEntry == null) { 
       return false; 
      } 
      final Long endOfRange = floorEntry.getValue(); 
      if (endOfRange >= n) { 
       return true; 
      } 
      return false; 
     } 

     @Override 
     public Iterator<T> iterator() { 
      throw new IllegalAccessError("Method not implemented. Left for the reader. (You'd need a custom Iterator class, I think)"); 
     } 

     @Override 
     public Object[] toArray() { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public <T> T[] toArray(T[] a) { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public boolean add(T e) { 
      if ((Long) e < 1L) { 
       throw new IllegalArgumentException("This example only supports counting numbers, mainly because it simplifies printGaps() later on"); 
      } 
      if (this.contains(e)) { 
       // Do nothing. Already in set. 
      } 
      final Long previousEntryKey; 
      final T eMinusOne = (T) (Long) (e-1L); 
      final T nextEntryKey = (T) (Long) (e+1L); 
      if (this.contains(eMinusOne)) { 
       // Find the greatest backingSet entry less than e 
       Map.Entry<T,T> floorEntry = backingMap.floorEntry(e); 
       final T startOfPrecedingRange; 
       startOfPrecedingRange = floorEntry.getKey(); 
       if (this.contains(nextEntryKey)) { 
        // This addition will join two previously separated ranges 
        T endOfRange = backingMap.get(nextEntryKey); 
        backingMap.remove(nextEntryKey); 
        // Extend the prior entry to include the whole range 
        backingMap.put(startOfPrecedingRange, endOfRange); 
        return true; 
       } else { 
        // This addition will extend the range immediately preceding 
        backingMap.put(startOfPrecedingRange, e); 
        return true; 
       } 
      } else if (this.backingMap.containsKey(nextEntryKey)) { 
       // This addition will extend the range immediately following 
       T endOfRange = backingMap.get(nextEntryKey); 
       backingMap.remove(nextEntryKey); 
       // Extend the prior entry to include the whole range 
       backingMap.put(e, endOfRange); 
       return true; 
      } else { 
       // This addition is a new range, it doesn't touch any others 
       backingMap.put(e,e); 
       return true; 
      } 
     } 

     @Override 
     public boolean remove(Object o) { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public boolean containsAll(Collection<?> c) { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public boolean addAll(Collection<? extends T> c) { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public boolean retainAll(Collection<?> c) { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public boolean removeAll(Collection<?> c) { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public void clear() { 
      this.backingMap.clear(); 
     } 

     @Override 
     public Comparator<? super T> comparator() { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public SortedSet<T> subSet(T fromElement, T toElement) { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public SortedSet<T> headSet(T toElement) { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public SortedSet<T> tailSet(T fromElement) { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public T first() { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     @Override 
     public T last() { 
      throw new IllegalAccessError("Method not implemented. Left for the reader."); 
     } 

     public void printGaps() { 
      Long lastContiguousNumber = 0L; 
      for (Map.Entry<T, T> entry : backingMap.entrySet()) { 
       Long startOfNextRange = (Long) entry.getKey(); 
       Long endOfNextRange = (Long) entry.getValue(); 
       if (startOfNextRange > lastContiguousNumber + 1) { 
        System.out.println(String.valueOf(lastContiguousNumber+1) + ".." + String.valueOf(startOfNextRange - 1)); 
       } 
       lastContiguousNumber = endOfNextRange; 
      } 
      System.out.println(String.valueOf(lastContiguousNumber+1) + "..infinity"); 
      System.out.println("Backing map size is " + this.backingMap.size()); 
      System.out.println(backingMap.toString()); 
     } 




    } 


    public static void main(String[] args) { 

     SE se = new SE(); 

     RangeSet<Long> testRangeSet = se.new RangeSet<Long>(); 

     // Start by putting 1,000,000 entries into the map with a few, pre-determined, hardcoded gaps 
     for (long i = 1; i <= 1000000; i++) { 
      // Our pre-defined gaps... 
      if (i == 58349 || (i >= 87333 && i <= 87777) || i == 303998) { 
       // Do not put these numbers in the set 
      } else { 
       testRangeSet.add(i); 
      } 
     } 

     testRangeSet.printGaps(); 

    } 
} 

И выход:

58349..58349 
87333..87777 
303998..303998 
1000001..infinity 
Backing map size is 4 
{1=58348, 58350=87332, 87778=303997, 303999=1000000} 
+1

Ваши входные данные также должны быть отсортированы, иначе резервная «Карта» станет большой, пока она не станет маленькой. –

+0

Если вы сортируете вход, вам не нужна карта. Вы просто выполняете необходимую процедуру по отсутствующим билетам, когда находите их в отсортированном потоке. – erickson

+0

Это правда, но для этого требуется, чтобы потоки были полностью упорядочены. ОП упомянул несколько «ежедневных файлов журнала». Я легко мог представить, что файлы журналов _mostly_ отсортированы для начала. Например, приложение получает уникальный номер билета из генератора последовательности, выполняет некоторую обработку и записывает запись журнала с номером билета по завершении. В зависимости от того, сколько времени займет обработка, некоторые из записей журнала могут быть не в порядке. Я упомянул о сортировке в качестве предостережения, но я ожидаю, что OP сможет использовать свои ежедневные журналы так, как они есть. Это только спекуляция с моей стороны. –

1

Хорошо, либо вы храните все в памяти, и вы рискуете переполнением кучи, или вы не храните его в памяти, и вам нужно много вычислить.

Я предлагаю что-то промежуточное - хранить минимальную необходимую информацию, необходимую во время обработки. Вы можете сохранить конечные точки известной не-щелевой последовательности в классе с двумя длинными полями. И все эти типы данных последовательностей могут храниться в отсортированном списке. Когда вы найдете новый номер, перейдите в список, чтобы увидеть, смежен ли он с одной из конечных точек. Если это так, измените конечную точку на новое целое число и проверьте, можете ли вы объединить соседние объекты последовательности (и, следовательно, удалить один из объектов). Если нет, создайте новый объект последовательности в правильно отсортированном месте.

Это будет O(n) в использовании памяти и O(n) в режиме CPU. Но использование любой структуры данных, которая хранит информацию обо всех номерах, будет просто n в использовании памяти и O(n*lookuptime) в CPU, если время поиска не выполняется в постоянное время.

+0

Почему downvote? Это не встроенная структура данных, но он также спросил, как он может решить свою проблему. – peternyc

+0

Я тоже не понимаю нисходящую стрелку – Tobia

+0

Я поднимусь, так как это было в основном тем, что я предложил. Я сохраню свой ответ, так как я дал конкретную реализацию, которая может быть полезна. Кроме того, вам может понадобиться избегать примечания «большой о-о» («O (n)»), пока вы не поймете это лучше - некоторые люди говорят о нем. Например, что-то, что требует времени «n + n * lookuptime» для завершения, по-прежнему остается «O (n)», как я понимаю. Не существует 'O (n + n ..)'. –

0

Я считаю, что это идеальный момент, чтобы ознакомиться с bloom-filter. Это замечательная вероятностная структура данных, которая может быть использована для немедленного доказательства того, что элемент не находится в наборе.

Как это работает? Идея довольно проста, ускорение становится более сложным, и реализация может быть найдена в Guava.

Идея

Инициализировать фильтр, который будет массив битов длины, которые позволили бы хранить максимальное значение используемого hash function. При добавлении элемента в набор вычислите его хэш. Определите, что такое бит 1 s и убедитесь, что все они переключаются на 1 в фильтр (массив). Если вы хотите проверить, находится ли элемент в наборе, просто вычислите его хэш, а затем проверьте, все ли биты, которые являются 1 s в хеш, равны 1 s в фильтре. Если какой-либо из этих битов является фильтром 0, элемент определенно не входит в набор. Если для всех из них установлено значение 1, элемент может находиться в фильтре, поэтому вам нужно будет пропустить все элементы. подпиточного

Простая вероятностная модель дает ответ на то, как большой фильтр (и диапазон хэш-функции) должна быть, чтобы обеспечить оптимальный шанс для false positive который является ситуация, что все биты 1 s но элемент не входит в набор.

Реализация

Реализация гуавы предоставляет следующий конструктор к bloom-filter: create(Funnel funnel, int expectedInsertions, double falsePositiveProbability). Вы можете настроить фильтр самостоятельно, в зависимости от expectedInsertions и falsePositiveProbability.

ложноположительных

Некоторые люди знают о bloom-filters из-за ложноположительных возможности. Фильтр Bloom может использоваться таким образом, чтобы не полагаться на флаг mightBeInFilter. Если это возможно, вы должны пропустить все элементы и проверить один за другим, если элемент находится в наборе или нет.

Возможное использование В вашем случае, я бы создать фильтр для набора, то после того, как все билеты будут добавлены просто пройдёмся по всем номерам (как вы должны петли в любом случае) и проверить, если они filter#mightBe Int задавать. Если вы установите falsePositiveProbability на 3%, вы достигнете сложности около O(n^2-0.03m*n), где m означает количество пробелов. Исправьте меня, если я ошибаюсь в оценке сложности.

0

Читайте столько номеров билетов, как вы можете поместить в доступную память.

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

После того, как все номера билетов были отсортированы во временные файлы, вы можете объединить их в один, отсортированный поток номеров билетов, искать пробелы.

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

Старые алгоритмы ленточных накопителей по-прежнему актуальны.

0

Вот идея: если вы заранее знаете, диапазон ваших чисел, то

предварительно вычислить сумму всех чисел, которые вы ожидаете, чтобы быть там. 2. Затем продолжайте читать свои номера и составляйте сумму всех прочитанных чисел, а также количество ваших номеров. 3. Если сумма, которую вы придумали, такая же, как и предварительно рассчитанная, тогда нет пробелов. 4. Если сумма отличается и количество ваших номеров коротким только на одно из ожидаемого числа, тогда предварительно рассчитанная сумма - фактическая сумма даст вам недостающее число. 5. Если количество ваших номеров короче более одного, то вы узнаете, сколько цифр не хватает и какова их сумма.

Лучшая часть состоит в том, что вам не нужно хранить коллекцию своих номеров в памяти.

+0

Если у меня есть сумма и количество недостающих чисел, а число равно больше 1, как я могу понять, какие они? – Tobia

+0

Чем больше число недостающих чисел, тем сложнее решение. Это предлагаемое решение будет работать только для ответа, если есть пробел вообще и для случая отсутствия пропущенного номера. Если есть больше, чем один недостающий номер, вам нужно будет сделать дополнительную работу, чтобы узнать, что это такое. Основным преимуществом моего решения является то, что он очень эффективен при использовании памяти. –

+0

Существует общее решение для нахождения k недостающих чисел из последовательности. В двух словах, вы вычисляете суммы для каждого номера билета, поднятого до мощности. Так как s1 = a1 + a2 + a3 + ..., s2 = a1^2 + a2^2 + a^3 + ..., ..., sk = a1^k + a2^k + a3^k + ... где k - количество отсутствующих элементов. Конечно, вы также можете вычислить разницу между этими суммами и тем, что они должны были бы, если бы присутствовали все числа. Это дает вам систему из k независимых уравнений, которая позволяет вам решить для k недостающих чисел. Это лучше всего работает, если вы знаете k заранее, но вы можете просто выбрать очень большой k. – erickson

Смежные вопросы