Biorąc pod uwagę Pythona list z bytes wartości:

# actual str values un-important
[
    b'foo',
    b'bar',
    b'baz',
    ...
]

Jak można podzielić listę na fragmenty, z których każdy ma maksymalny rozmiar pamięci poniżej określonego pułapu?

Na przykład: gdyby górna granica wynosiła 7 bajtów, oryginalna lista została podzielona na listę list

[
    [b'foo', b'bar'], # sublist 0
    [b'baz'], # sublist 1
    ...
]

Każda podlista miałaby co najwyżej 7 bajtów, w oparciu o łączną długość zawartości listy.

Uwaga: każda podlista powinna być maksymalnie zapakowana w kolejności pierwotnej listy. W powyższym przykładzie pierwsze 2 wartości str zostały zgrupowane, ponieważ jest to maksimum możliwe w ramach limitu 7 bajtów.

Z góry dziękujemy za uwagę i odpowiedź.

7
Ramón J Romero y Vigil 1 kwiecień 2020, 00:54

4 odpowiedzi

Najlepsza odpowiedź

To rozwiązanie dotyczy functools.reduce.

l = [b'abc', b'def', b'ghi', b'jklm', b'nopqrstuv', b'wx', b'yz']

reduce(lambda a, b, size=7: a[-1].append(b) or a if a and sum(len(x) for x in a[-1]) + len(b) <= size else a.append([b]) or a, l, [])

a to puste list, a b to element z oryginału list.

if a and sum(len(x) for x in a[-1]) + len(b) <= size
sprawdź, czy a nie jest puste i suma długości bytes w ostatnim dołączonym list i długość b nie przekracza size.

a[-1].append(b) or a
dołącz b do ostatniego dołączonego list z a i zwróć a, jeśli warunek to True.

a.append([b]) or a
zrób list z b i dołącz nowe list do a i zwróć a

Wynik;

[[b'abc', b'def'], [b'ghi', b'jklm'], [b'nopqrstuv'], [b'wx', b'yz']]
2
Nizam Mohamed 8 kwiecień 2020, 05:13

Problem optymalnego podziału sekwencji tak, aby elementy spełniały dany warunek max / min przy zachowaniu kolejności elementów, można rozwiązać chciwie. W związku z tym wystarczy powtórzyć sekwencję wejściową tylko raz i zachować bufor elementów. W Pythonie można to elegancko zakodować za pomocą generatora, który będzie miał tę zaletę, że nie będzie musiał tworzyć wyniku.

Większość algorytmu dla twojego problemu jest następująca:

def split_by_size(items, max_size, get_size=len):
    buffer = []
    buffer_size = 0
    for item in items:
        item_size = get_size(item)
        if buffer_size + item_size <= max_size:
            buffer.append(item)
            buffer_size += item_size
        else:
            yield buffer
            buffer = [item]
            buffer_size = item_size
    if buffer_size > 0:
        yield buffer

Gdzie ostatni parametr deleguje kwestię określenia rozmiaru danego elementu do określonej wywoływalnej. Nie będę się nad tym rozwodzić, ale założę, że wystarczy prosty len(). Zakłada się również, że każdy element z osobna spełniałby warunek, w przeciwnym razie należy załatwić również ten przypadek.

Testowanie powyższego kodu:

import random


k = 10
n = 15
max_size = 10

random.seed(0)
items = [b'x' * random.randint(1, 2 * k // 3) for _ in range(n)]
print(items)
# [b'xxxx', b'xxxx', b'x', b'xxx', b'xxxxx', b'xxxx', b'xxxx', b'xxx', b'xxxx', b'xxx', b'xxxxx', b'xx', b'xxxxx', b'xx', b'xxx']

print(list(split_by_size(items, k)))
# [[b'xxxx', b'xxxx', b'x'], [b'xxx', b'xxxxx'], [b'xxxx', b'xxxx'], [b'xxx', b'xxxx', b'xxx'], [b'xxxxx', b'xx'], [b'xxxxx', b'xx', b'xxx']]

Ponadto, jeśli mimo wszystko chcesz zapisać wynik podziału w list, kod powyższego podejścia może być nieco bardziej zwarty:

def chunks_by_size(items, max_size, get_size=len):
    result = []
    size = max_size + 1
    for item in items:
        item_size = get_size(item)
        size += item_size
        if size > max_size:
            result.append([])
            size = item_size
        result[-1].append(item)
    return result

Ale także nieco wolniej (patrz testy porównawcze poniżej).


Możesz też pomyśleć o użyciu functools.reduce() (w zasadzie to samo co @NizamMohamed answer), a kod będzie krótszy, ale być może mniej czytelny:

def chunks_by_size_reduce(items, size, get_size=len):
    return functools.reduce(
        lambda a, b, size=size:
            a[-1].append(b) or a
            if a and sum(get_size(x) for x in a[-1]) + get_size(b) <= size
            else a.append([b]) or a, items, [])

I na pewno mniej wydajne, ponieważ get_size() jest wywoływane dla każdego elementu listy wewnętrznej „kandydata” dla każdego rozważanego elementu, co sprawia, że O(n k!), gdzie k jest średnią liczbą elementów w każdym sekwencja podrzędna. W przypadku niektórych czasów zobacz testy porównawcze poniżej.


Nie zdziwiłbym się rozwiązaniem wykorzystującym itertools.accumulate(), ale byłoby to również dość powolne.


Najprostszym podejściem do przyspieszenia byłoby użycie Cython lub Numba. Tutaj zostało to zastosowane do split_by_size(). Dla obu kod pozostałby niezmieniony.

Porównując wszystko, co otrzymujemy (_cy oznacza wersję skompilowaną przez Cythona, a _nb wersję skompilowaną przez Numba):

%timeit list(split_by_size(items * 100000, k + 1))
# 10 loops, best of 3: 281 ms per loop
%timeit list(split_by_size_cy(items * 100000, k + 1))
# 10 loops, best of 3: 181 ms per loop
%timeit list(split_by_size_nb(items * 100000, k + 1))
# 100 loops, best of 3: 5.17 ms per loop
%timeit chunks_by_size(items * 100000, k + 1)
# 10 loops, best of 3: 318 ms per loop
%timeit chunks_by_size_reduce(items * 100000, k + 1)
# 1 loop, best of 3: 1.18 s per loop

Zauważ, że chociaż wersja skompilowana przez Numba jest znacznie szybsza niż alternatywy, jest również najbardziej krucha, ponieważ wymaga flagi forceobj ustawionej na True, co może prowadzić do niestabilnego wykonania.

W każdym razie nie wierzę, że byłoby to wąskim gardłem, jeśli ostatecznym celem jest wysłanie zgrupowanych elementów przez jakąś operację we / wy.


Zwróć uwagę, że algorytm jest prawie taki sam, jak inne odpowiedzi, po prostu uważam, że kod tutaj jest nieco bardziej przejrzysty.

4
norok2 8 kwiecień 2020, 20:47

Prostym, naiwnym podejściem byłoby:

import sys
import numpy as np

# init input data - as per the comments, data type does matter, 
# for memory calculation, and for the sake of example -
# string is probably the easiest case:

lts=list("abcdefghijklmnopqrstuvwxyz")

data=[{letter: "".join(np.random.choice(lts, np.random.randint(100, 700)))} for letter in lts]

# parameters setup:

threshold=1024
buffer=[]
buffer_len=0
res_data=[]

for el in data:
    len_=sys.getsizeof(list(el.values())[0]) # I assumed it's one key, one value per dictionary (looks like this from your question) 
    if(buffer_len+len_>threshold):
        res_data.append(buffer)
        buffer=[el]
        buffer_len=len_
    else:
        buffer.append(el)
        buffer_len+=len_

if(buffer_len>0):
    res_data.append(buffer)

print(res_data)
1
Grzegorz Skibinski 31 marzec 2020, 23:02

Mówiąc krótko i słodko:

l = [b'foo', b'bar', b'baz']

thresh = 7
out = []
cur_size = 0
for x in l:
    if len(x) > thresh:
        raise ValueError("str too big")
    if cur_size + len(x) > thresh:
        cur_size = 0
    if cur_size == 0:
        out.append([])
    out[-1].append(x)
    cur_size += len(x)

print(out)

Spowoduje to wyświetlenie:

[[b'foo', b'bar'], [b'baz']]

To powinno być to, czego chcesz, jeśli dobrze zrozumiałem. To jest bardzo proste; Wszystko, co robi, to dołącza ciągi z listy i sprawdza łączny rozmiar wszystkiego na bieżącej liście, do której jest dołączany - jeśli rozmiar plus następny element będzie większy niż próg, uruchamia się ponownie.

1
xilpex 4 kwiecień 2020, 01:35