Блог

просто интересно, существует ли лучшее решение для такого рода проблем.

Мы знаем, что для процентного разделения четного числа по X / Y мы можем получить точное разделение данных — например, для размера данных 10:

 10 * .6 = 6
10 * .4 = 4
          10 
  

Разделение данных таким образом легко, и мы можем гарантировать, что у нас есть все данные и ничего не потеряно. Однако там, где я испытываю трудности, используются менее понятные числа — возьмите 11

 11 * .6 = 6.6
11 * .4 = 4.4
          11
  

Однако мы не можем индексировать в массив, например, в i = 6.6 . Итак, мы должны решить, как это сделать. Если мы возьмем ТОЛЬКО целочисленную часть, мы потеряем 1 точку данных —

 First set = 0..6
Second set = 6..10
  

Это был бы тот же случай, если бы мы разбили числа на пол.

Однако, если мы возьмем верхний предел чисел:

 First set = 0..7
Second set = 7..12
  

И мы прочитали дальше конца нашего массива.

Это становится еще хуже, когда мы вводим 3-й или 4-й раздел (например, 30,30,20,20).

Существует ли стандартная процедура разделения для такого рода проблем? Допустима ли потеря данных? Похоже, что потеря данных была бы неприемлемой для зависимых данных, таких как временные ряды.

Спасибо!

РЕДАКТИРОВАТЬ: Значения .6 и .4 выбираются мной. Это могут быть любые два числа, сумма которых равна 1 .

Прежде всего, обратите внимание, что ваша проблема не ограничивается массивами нечетного размера, как вы утверждаете, а массивами любого размера. Как бы вы разделили массив из 10 элементов на 56-44%? Или разделение массива из 4 элементов на 60% -40%?

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

Это может быть нормально в большинстве случаев, когда это одноразовое вычисление и точность не требуется. Вы должны спросить себя, каковы ваши требования. Например: вы берете тысячи массивов размером 10 и каждый раз, когда вы разбиваете их на 56-44%, выполняете какие-то вычисления и возвращаете результат? Вы должны спросить себя, какую точность вы хотите. Вас волнует, будет ли ваш результат разделен на 60% -40% или на 50% -50%?

В качестве другого примера представьте, что вы выполняете равное разделение в 4 стороны на 25%-25%-25%-25%. Если у вас есть 10 элементов и вы применяете метод округления, в итоге получается 3,3,3,1 элемента. Конечно, это испортит ваши результаты.

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

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

Итак, представьте, что вам нужно разделить массив размером 10 на 56-44%. Это означает, что вам нужно разделить его на 5,6 и 4,4 элемента в среднем.

Существует много способов добиться среднего значения в 5,6 элемента. Самый простой вариант (и с наименьшей разницей в последовательности попыток) — это иметь в 60% случаев набор из 6 элементов и в 40% случаев набор из 5 элементов.

0.6*6 0.4*5 = 5.6

С точки зрения кода это то, что вы можете сделать, чтобы каждый раз определять размер набора:

 import random

array_size = 10
first_split = 0.56
avg_split_size = array_size * first_split 
floored_split_size = int(avg_split_size)

if avg_split_size > floored_split_size:
    if random.uniform(0,1) > avg_split_size - floored_split_size:
        this_split_size = floored_split_size
    else: 
        this_split_size = floored_split_size   1    
else:
    this_split_size = avg_split_size
  

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

Вместо использования ciel() или floor() используйте round() вместо этого. Например:

 >>> round(6.6)
7.0
  

Возвращаемое значение будет иметь float тип. Для получения целочисленного значения введите его в int виде:

 >>> int(round(6.6))
7
  

Это будет значение вашего первого разделения. Для получения второго разделения вычислите его с помощью len(data) - split1_val . Это будет применимо в случае проблемы с разделением на 2 части.

В случае разделения на 3, округлите значение двух разделений и примите значение 3-го разделения в качестве значения len(my_list) - val_split_1 - val_split2

В общем виде, для N split:

Возьмите round() значение N-1 split. И для последнего значения выполните len(data) — «значение из N значений round()».

где len() указывается длина списка.

Давайте сначала рассмотрим простое разделение набора на две части.

Пусть n — количество элементов, которые мы разделяем, а p и q — пропорции, так что

p q == 1

Я утверждаю, что части после десятичной запятой всегда будут суммироваться с 1 или 0 , поэтому мы должны использовать floor для одного и ceil для другого, и мы всегда будем правы.

Вот функция, которая делает это вместе с тестом. Я оставил инструкции print в, но они закомментированы.

 def simpleSplitN(n, p, q):
    "split n into proportions p and q and return indices"
    np = math.ceil(n*p)
    nq = math.floor(n*q)
    #print n, sum([np, nq]) #np and nq are the proportions
    return [0, np] #these are the indices we would use

#test for simpleSplitN
for i in range(1, 10):
    p = i/10.0;
    q = 1-p
    simpleSplitN(37, p, q);
  

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

-----------------------

Мы можем выразить p*n как n/(1/p) , и поэтому с помощью алгоритма деления мы получаем целые числа k и r

n == k*(1/p) r с 0 <= r < (1/p)

Таким образом r/(1/p) == p*r < 1

Мы можем сделать точно то же самое для q , получив

q*r < 1 (это другой r)

Важно отметить, что q*r и p*r являются частью после запятой, когда мы делим наше n .

Теперь мы можем сложить их вместе (теперь мы добавили индексы)

0 <= p*(r_1) < 1
0 <= q*(r_2) < 1

=> 0 < p*r q*r == p*n q*n k_1 k_2 == n k_1 k_2 < 2

Но при замыкании целых чисел n k_1 k_2 является целым числом и поэтому

0 < n k_1 k_2 < 2

означает, что p*r q*r должно быть либо 0 , либо 1 . Это будет только 0 в том случае, если наши n данные разделены равномерно.

В противном случае теперь мы можем видеть, что наши дробные части всегда будут суммироваться с 1 .

-----------------------

Мы можем выполнить очень похожее (но немного более сложное) доказательство для разделения n на произвольное число (скажем N ) частей, но вместо их суммирования до 1 , они будут суммироваться до целого числа, меньшего N .

Вот общая функция, она имеет раскомментированные инструкции печати для целей проверки.

 import math
import random

def splitN(n, c):
    """Compute indices that can be used to split
    a dataset of n items into a list of proportions c
    by first dividing them naively and then distributing
    the decimal parts of said division randomly
    """
    nc = [n*i for i in c];
    nr = [n*i - int(n*i) for i in c] #the decimal parts
    N = int(round(sum(nr)))          #sum of all decimal parts
    print N, nc
    for i in range(0, len(nc)):
        nc[i] = math.floor(nc[i])
    for i in range(N):                  #randomly distribute leftovers
        nc[random.randint(1, len(nc)) - 1]  = 1
    print n,sum(nc);                    #nc now contains the proportions
    out = [0]                           #compute a cumulative sum
    for i in range(0, len(nc) - 1):
        out.append(out[-1]   nc[i])
    print out
    return out

#test for splitN with various proportions
c = [.1,.2,.3,.4]
c = [.2,.2,.2,.2,.2]
c = [.3, .2, .2, .3]
for n in range( 10, 40 ):
    print splitN(n, c)
  

Если у нас останутся остатки, мы никогда не получим равномерного разделения, поэтому мы распределяем их случайным образом, как сказал @Thanassis. Если вам не нравится зависимость от random , то вы могли бы просто добавить их все в начале или через равные промежутки времени.

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