Trộn ngẫu nhiên 5 gigabyte dữ liệu khó khăn

Question

Tôi đang đào tạo mạng nơron với khoảng năm gigabyte dữ liệu được lưu trữ dưới dạng mảng numpy. Dữ liệu được chia thành các khối 100000 hàng và tôi đã thực hiện sáu chu kỳ đào tạo trên tất cả các khối theo thứ tự ngẫu nhiên. Thật không may, mạng đã bắt đầu quá mức. Tôi nghĩ rằng nó vẫn có khả năng phù hợp với dữ liệu chặt chẽ hơn; sự nghi ngờ của tôi là các quy tắc nội bộ trong mỗi đoạn đều bắt đầu mâu thuẫn với nhau, và tôi cần trộn dữ liệu kỹ lưỡng hơn để nó có thể tập trung vào các kết hợp khác nhau. Tôi muốn thử điều này trước khi gặp khó khăn trong việc thu thập thêm dữ liệu đào tạo.

Có ai biết cách tốt để tạo ra một hoán vị mới có 3.6 triệu hàng (rất dài) dữ liệu không? Tôi đã nghĩ về cách sử dụng các kỹ thuật one of these, nhưng viết các mảng này bằng cách sử dụng numpy.savetxt tạo ra không thể tin được tệp lớn và tôi không thể biết cách thao tác các hàng riêng lẻ từ tệp chuẩn npy theo cách giúp giải quyết vấn đề này.

Hiện tại, ý tưởng tốt nhất của tôi là tạo hoán vị các chỉ mục được ghép nối (c, r) vào dữ liệu, trong đó c chọn một đoạn và r chọn một hàng từ đoạn đó. Tôi có thể lưu trữ mỗi hàng trong một mảng preallocated mới, và sau đó lưu nó. Nhưng tôi tự hỏi nếu có một giải pháp I/O ràng buộc ít khủng khiếp hơn. Có một số nguyên tắc để trộn các cặp ngẫu nhiên của khối với nhau cho đến khi bạn nhận được một hoán vị đó là độc lập về mặt thống kê từ hoán vị bắt đầu?

Answer 1

Trong số những điều tôi đã cố gắng cho đến nay, giải pháp PyTables hiện là tốt nhất, tiếp theo là giải pháp sử dụng hỗ trợ của numpy cho mảng được ghi nhớ. Các giải pháp PyTables là không đơn giản mặc dù.Nếu bạn sử dụng một mảng xáo trộn của các số nguyên để trực tiếp chỉ mục một mảng PyTables, nó rất chậm. Nhanh hơn nhiều là quy trình gồm hai bước sau:

1. Chọn một tập hợp con ngẫu nhiên của mảng sử dụng mảng chỉ mục boolean. Điều này phải được thực hiện theo cách chunkwise. Nếu bạn truyền mảng chỉ mục trực tiếp vào mảng PyTables, nó sẽ chậm.
   • Preallocate một mảng numpy và tạo danh sách các lát tách mảng PyTables thành các khối.
   • Đọc từng đoạn hoàn toàn vào bộ nhớ, sau đó sử dụng đoạn tương ứng của mảng chỉ mục để chọn giá trị chính xác cho đoạn đó.
   • Lưu trữ các giá trị đã chọn trong mảng được phân bổ trước.
2. Sau đó, xáo trộn mảng được phân bổ trước.

Quy trình này tạo ra hoán vị ngẫu nhiên như quy trình xáo trộn bình thường. Nếu điều đó không rõ ràng, hãy xem xét điều này: (n choose x) * x! = x! * n!/(x! * (n - x)!) = n!/(n - x)!. Phương pháp này đủ nhanh để thực hiện tải ngẫu nhiên cho mỗi chu kỳ đào tạo. Nó cũng có thể nén dữ liệu xuống ~ 650M - gần như giảm 90%.

Đây là triển khai hiện tại của tôi; điều này được gọi một lần cho mỗi đoạn đào tạo trong kho văn bản. (Các mảng trở lại được xáo trộn ở những nơi khác.)

def _h5_fast_bool_ix(self, h5_array, ix, read_chunksize=100000): 
    '''Iterate over an h5 array chunkwise to select a random subset 
    of the array. `h5_array` should be the array itself; `ix` should 
    be a boolean index array with as many values as `h5_array` has 
    rows; and you can optionally set the number of rows to read per 
    chunk with `read_chunksize` (default is 100000). For some reason 
    this is much faster than using `ix` to index the array directly.''' 

    n_chunks = h5_array.shape[0]/read_chunksize 
    slices = [slice(i * read_chunksize, (i + 1) * read_chunksize) 
       for i in range(n_chunks)] 

    a = numpy.empty((ix.sum(), h5_array.shape[1]), dtype=float) 
    a_start = 0 
    for sl in slices: 
     chunk = h5_array[sl][ix[sl]] 
     a_end = a_start + chunk.shape[0] 
     a[a_start:a_end] = chunk 
     a_start = a_end 

    return a 

Đó là hơi điên với tôi rằng một O (n^2) (phương pháp lặp qua mảng toàn bộ PyTables cho mỗi đoạn) là nhanh hơn trong trường hợp này hơn một O (n) cách tiếp cận (chọn ngẫu nhiên mỗi hàng trong một lần). Nhưng này, nó hoạt động. Với một chút gián tiếp hơn, điều này có thể được điều chỉnh để tải các hoán vị không ngẫu nhiên, nhưng điều đó làm tăng thêm độ phức tạp hơn giá trị của nó ở đây.

Giải pháp mmap có tại đây để tham khảo, đối với những người cần giải pháp nguyên chất vất vả vì bất kỳ lý do gì. Nó xáo trộn tất cả các dữ liệu trong khoảng 25 phút, trong khi các giải pháp trên quản lý giống nhau trong ít hơn một nửa thời gian đó. Điều này cũng nên được quy mô tuyến tính, bởi vì mmap cho phép (tương đối) truy cập ngẫu nhiên hiệu quả.

import numpy 
import os 
import random 

X = [] 
Y = [] 

for filename in os.listdir('input'): 
    X.append(numpy.load(os.path.join('input', filename), mmap_mode='r')) 

for filename in os.listdir('output'): 
    Y.append(numpy.load(os.path.join('output', filename), mmap_mode='r')) 

indices = [(chunk, row) for chunk, rows in enumerate(X) 
         for row in range(rows.shape[0])] 
random.shuffle(indices) 

newchunks = 50 
newchunksize = len(indices)/newchunks 

for i in range(0, len(indices), newchunksize): 
    print i 
    rows = [X[chunk][row] for chunk, row in indices[i:i + newchunksize]] 
    numpy.save('X_shuffled_' + str(i), numpy.array(rows)) 
    rows = [Y[chunk][row] for chunk, row in indices[i:i + newchunksize]] 
    numpy.save('Y_shuffled_' + str(i), numpy.array(rows)) 

Answer 2

Giả định sau đây dữ liệu của bạn đã được chia thành các bản ghi có thể truy xuất dễ dàng của một số loại. (Tôi không biết nếu có một định dạng tập tin tiêu chuẩn cho numpy dữ liệu.)

1. Tạo một chỉ số của các dữ liệu trong các hình thức của một dict, lập bản đồ mỗi ID kỷ lục độc đáo (0 đến n-1) với một số phương tiện tìm lại dữ liệu. Ví dụ: nếu tất cả trong một tệp nhị phân, bạn sẽ lưu trữ một bộ dữ liệu có dạng (file_offset, record_length). Không cần phải giữ bản thân dữ liệu.

2. Tạo một danh sách các n yếu tố, bao gồm các phím của chỉ số dict (một lần nữa, từ 0 đến n-1).

3. Trộn danh sách ID bản ghi. (Cung cấp bộ tạo số ngẫu nhiên của riêng bạn, nếu cần.)

4. Mở một tệp mới (hoặc bất kỳ thứ gì) để chứa dữ liệu xáo trộn.

5. Đọc ID bản ghi trong danh sách từ đầu đến cuối. Đối với mỗi ID bản ghi, hãy tìm vị trí của bản ghi đó trong chỉ mục. Lấy dữ liệu tại vị trí đó và nối nó vào tệp đầu ra.

Pseudo-code:

# This assumes a binary file of unequal-length 
# records. It also assumes that the file won't 
# be changed while we're doing this. 

# Create index. 
index = {} 
rec_offset = 0 
for rec_id, record in original_data.iterate_records(): 
    # This bit depends greatly on how your data 
    # is stored... 
    rec_length = len(record) 
    index[rec_id] = (rec_offset, rec_length) 
    rec_offset += rec_length 

# Shuffle. 
num_records_indexed = rec_id + 1 # rec_id is still in scope. 
records_order = list(range(num_records_indexed)) 
records_order = random.shuffle(records_order, "<optional_RNG_here>") 

# Create new shuffled-data file. 
with open("output_file.bin", "wb") as output: 
    for rec_id in records_order: 
     rec_offset, rec_length = index[rec_id] 
     record = original_data.get_rec_at(rec_offset, rec_length) 
     output.write(record) 

Indexing, xáo trộn, và de-indexing đều O (n), do đó phần tồi tệ nhất nên I/O: đọc dữ liệu và sau đó sao chép nó (đọc lần thứ hai, cộng với ghi).