Как я могу сгруппировать большой набор данных

Question

У меня есть простой текстовый файл, содержащий два столбца, оба целых числа

1 5
1 12
2 5
2 341
2 12

и т. Д.

Мне нужно сгруппировать набор данных по второму значению, так что вывод будет.

5 1 2
12 1 2
341 2

Теперь проблема в том, что файл очень большой, размером около 34 Гб, я попытался написать скрипт на Python, чтобы сгруппировать их в словарь со значением в виде массива целых чисел, но все равно он занимает много места.слишком долго.(Я полагаю, что на выделение array('i') и расширение их на append требуется большое время. Сейчас я планирую написать сценарий PIG, который планирую запустить на псевдораспределенной машине hadoop (Экземпляр Amazon EC3 High Memory Large).

data = load 'Net.txt';
gdata = Group data by $1; // I know it will lead to 5 (1,5) (2,5) but thats okay for this snippet
store gdata into 'res.txt';

Я хотел бы знать, есть ли какой-нибудь более простой способ сделать это.

Обновление: сохранение такого большого размерафайл в памяти не подлежит сомнению. В случае решения на Python я планировал провести 4 запуска в первом запуске, учитываются только значения второго столбца от 1 до 10 миллионов, в следующем - от 10 до 20 миллионов и так далее.но это оказалось очень медленным.

Решение pig / hadoop интересно, потому что оно хранит все на диске [ну, большинство из них].

Для лучшего понимания этот набор данных содержит информацию о подключениииз ~ 45 миллионов пользователей Твиттера, а формат файла означает, что идентификатор пользователя, заданный вторым числом, следует за первым.

Итаклосьон, который я использовал:

class AdjDict(dict):
    """
     A special Dictionary Class to hold adjecancy list
    """
    def __missing__(self, key):
        """
        Missing is changed such that when a key is not found an integer array is initialized
        """
        self.__setitem__(key,array.array('i'))
        return self[key]

Adj= AdjDict()

for line in file("net.txt"):
    entry =  line.strip().split('\t')
    node = int(entry[1])
    follower = int(entry[0])
    if node < 10 ** 6:
        Adj[node].append(follower)

# Code for writting Adj matrix to the file:

Answer 1

Если у вас ~ 17 символов в строке (число, которое я выбрал случайным образом, чтобы упростить математику), у вас в этом файле около 2 миллиардов записей. Если вы не работаете с большой физической памятью в 64-битной системе, вы уничтожите свой файл подкачки до смерти, пытаясь удержать все это в памяти в один голос. И это просто для чтения в виде структуры данных - предполагается, что после построения этой структуры вы действительно планируете делать что-то с ней.

С таким простым форматом данных, я думаю, вам лучше сделать что-то на C, а не на Python. Взломать эти данные не должно быть сложно, и вы будете иметь гораздо меньше накладных расходов. Как минимум, просто хранить 2 миллиарда 4-байтовых целых чисел было бы 8 Гб (если только вы не можете сделать некоторые упрощающие предположения о возможном диапазоне значений, которые вы в настоящее время перечисляете как 1 и 2), если они будут вписываться в байты или короткие, тогда вы можете использовать меньшие переменные типа int, что будет стоить хлопот для набора данных такого размера).

Answer 2

У меня было аналогичное требование, и вам просто нужно еще одно утверждение свиньи, чтобы убрать избыточности в 5 (1,5) (2,5).

a = LOAD 'edgelist' USING PigStorage('\t') AS (user:int,following:int);
b = GROUP a BY user;
x = FOREACH b GENERATE group.user, a.following;
store x INTO 'following-list';

Answer 3

Если вы работаете с файлом размером 34 ГБ, я предполагаю, что жесткий диск, как с точки зрения хранения, так и времени доступа, не является проблемой.Как насчет чтения пар последовательно, и когда вы найдете пару (x, y), откройте файл "x", добавьте "y" и закройте файл "x"?В конце у вас будет один файл для каждого идентификатора пользователя Twitter, и каждый файл содержит всех пользователей, к которым он подключен.Затем вы можете объединить все эти файлы, если хотите, чтобы ваш результат был в указанном вами формате вывода.

---

ЭТО СКАЗАЛ ОДНА , я действительно считаю, что: (a) длятакой большой набор данных, точное разрешение не подходит, и что (b), вероятно, существует какой-то лучший способ измерения подключения, поэтому, возможно, вы хотели бы рассказать нам о своей конечной цели.

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

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

Answer 4

Может быть, вы можете сделать несколько проходов через файл.

Каждый диапазон ключей проходит через файл, например, если вы выбрали размер диапазона 100

1-й проход - отработать все ключи от 0-99
2-й проход - отработать все ключи от 100-199
3-й проход - отработать все ключи от 200-299
4й проход - отработать все ключи от 300-399
..и так далее.

для вашего образца, 1-й проход будет выводить

5 1 2
12 1 2

и 4-й проход выдаст

341 2

Выберите размер диапазона так, чтобы создаваемый вами дикт соответствовал вашей оперативной памяти

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

Answer 5

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

Первый будет работать с 500-мегабайтными фрагментами файла, обмениваясь столбцами и записывая результат в новые файлы. (Вы получите 70 или больше.) (Это не займет много памяти.)

Тогда я бы назвал поставляемую ОС sort(1) для каждого небольшого файла. (Это может занять несколько гигабайт памяти.)

Тогда я бы написал программу сортировки слиянием, которая бы объединяла строки из всех 70 с лишним подфайлов. (Это не займет много памяти.)

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

5 1
5 2
12 1
12 2

и вам нужно будет вернуть:

5 1 2
12 1 2

(Это не займет много памяти.)

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