Биннинг во времени

12

Задача в этой задаче состоит в том, чтобы поместить элементы массива в временные интервалы. Входные данные будут неубывающим массивом натуральных чисел, представляющих время событий, и целым числом, которое представляет размер каждого бина. Давайте начнем с примера. Мы называем входной массив Aи выходной массив O.

`A = [1,1,1,2,7,10]` and `bin_size = 2`.

`O = [4,0,0,1,1]`.

Почему ? С a bin_size = 2у нас будут следующие интервалы: (0,2], (2,4], (4,6], (6,8], (8,10]где четыре элемента (1,1,1,2)находятся в первом интервале (0,2], ни один во втором и третьем интервалах, один 7в интервале (6,8]и один 10в интервале (8,10].

Ваш код должен учитывать каждый интервал длины, bin_sizeначиная с, 0и подсчитывать количество чисел Aв каждом. Вы всегда должны включать в правом конце интервала в бункере так и в приведенном выше примере 2включается в подсчет 4. Ваш код должен работать за линейное время в сумме длин входных и выходных данных.

Больше примеров:

`A = [1,2,7,12,15]`  and `bin_size = 5`.

`O = [2, 1, 2]`.

`A = [1,2,7,12,15]`  and `bin_size = 3`.

`O = [2,0,1,1,1]`.

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

code-golf restricted-complexity
источник
0Разрешены ли выходы с трейлингом ? Так что вернемся [2,0,1,1,1,0]вместо [2,0,1,1,1]?
Кевин Круйссен
Нет завершающих нулей, пожалуйста.
2
Как насчет ситуаций, когда максимальное значение массива не кратно bin_size, мы должны действительно обрабатывать это? Кажется, что большинство ответов так и есть, но если это так, было бы неплохо добавить контрольный пример для этого сценария, чтобы избежать путаницы.
Кирилл Л.
@KirillL. Да, они должны быть обработаны тоже.
1
@GPS 0 не является положительным целым числом. Это не случайность :)

Ответы:

9

R , 48 байтов

function(n,s)table(cut(n,0:ceiling(max(n)/s)*s))

Попробуйте онлайн!

Еще раз, tableи cutтины к factorделать трюк для биннинга. Выходы поименованный vectorгде namesнаходятся интервалы, в интервальной нотации, например, (0,5].

РЕДАКТИРОВАТЬ: вернуться к более ранней версии, которая работает, когда sне делится n.

Giuseppe
источник
Я действительно не R, но на TIO это, кажется, выводит format you [most likely do not] find convenientбез tableчасти.
мое местоимение monicareinstate
@ кто-то, именно поэтому он там. cutразбивает вектор на факторы с уровнями, заданными интервалами, и tableподсчитывает вхождения каждого уникального значения в его входных данных.
Джузеппе
1
@ Кто-то, ах, я понял, я неправильно понял ваш комментарий. Нет, я думаю, что это не будет действительным, так как нам нужно количество каждого бина.
Джузеппе
1
Не полностью протестированы, но я думаю , что вы можете сэкономить пару байт reaplacing 0:ceiling(max(n)/s)*sс seq(0,max(n)+s-1,s). Это работает по крайней мере для двух образцов в вопросе.
Грегор Томас
1
@ Грегор Хмм, если это сработает, 1:max(n/s+1)*s-sэто еще одно улучшение, так как оба они эквивалентны
Джузеппе
6

Октава , 36 байт

@(A,b)histc(A,1:b:A(end)+b)(1:end-1)

Попробуйте онлайн!

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

Стьюи Гриффин
источник
3

Perl 5 -a -i , 32 28 байт

Дайте счет после опции -i. Дайте каждый элемент ввода в отдельной строке на STDIN

$G[~-$_/$^I]--}{say-$_ for@G

Попробуйте онлайн!

Тон Хоспел
источник
2
Это впечатляет.
3

Python 2 , 62 байта

I,s=input()
B=[0]*(~-I[-1]/s+1)
for i in I:B[~-i/s]+=1
print B

Попробуйте онлайн!

Мертвый Опоссум
источник
1
Прежде всего: хороший ответ, я уже добавил +1 (и создал порт на Java, потому что он немного короче, чем у меня). Замыкающие нули, однако, недопустимы (просто спросили OP), поэтому I[-1]/s+1должны быть ~-I[-1]/s+1вместо.
Кевин Круйссен
@KevinCruijssen Спасибо за уведомление!
Мертвый опоссум
3

05AB1E , 18 байт

θs/Å0¹vDyI/î<©è>®ǝ

Попробуйте онлайн!

Emigna
источник
Я не очень хорошо знаю 05AB1E, но это, кажется, вызывает A.count max (A) , поэтому время выполнения не линейно в len (A) + len (O) . Это правильно или я что-то не так понял?
Денис
Счет Денниса был бы O(max(A)*max(A))... таким образом, он был квадратичным по максимуму А ... ОП указал, что он должен быть линейным с точки зрения ... что именно?
Магическая урна с осьминогом
2
@MagicOctopusUrn Ваш код должен выполняться за линейное время в сумме длин входных и выходных данных в соответствии с последней редакцией.
Деннис
2
@ Денис, который кажется довольно произвольным.
Волшебная Осьминог Урна
2
@MagicOctopusUrn Это единственное разумное определение линейного времени для этого вопроса, я думаю.
2

APL + WIN, 23 байта

Запрашивает ввод на экран бинов, а затем вектор целых чисел:

+⌿<\v∘.≤b×⍳⌈⌈/(v←⎕)÷b←⎕

Объяснение:

⎕ Prompt for input

⌈⌈/(v←⎕)÷b←⎕ divide the integers by bin size, take maximum and round up for number of bins

b×⍳ take number of bins from previous step and create a vector of bin upper boundaries

v∘.≤ apply outer product to generate boolean matrix where elements of vector ≤ boundaries

<\ switch off all 1's after first 1 in each row to filter multiple bin allocations

+⌿ sum columns for the result
Грэхем
источник
2

Java 8, 75 байт

a->b->{var r=new int[~-a[a.length-1]/b+1];for(int i:a)r[~-i/b]++;return r;}

Порт ответа @ DeadPossum на Python 2 , поэтому обязательно подтвердите его ответ!

Объяснение:

Попробуйте онлайн.

a->b->{          // Method with integer-array and integer parameters and no return-type
  var r=new int[~-a[a.length-1]/b+1];
                 //  Result integer-array of size `((last_item-1)/bin_length)+1`
  for(int i:a)   //  Loop over the input-array
    r[~-i/b]++;  //   Increase the value at index `(i+1)/bin_length` by 1
  return r;}     //  Return the result-array
Кевин Круйссен
источник
2

JavaScript (ES6), 60 байт / O (len (a) + max (a) / n)

Сохранено 5 байтов благодаря @Neil

Принимает ввод в синтаксисе карри (a)(n).

a=>n=>[...a.map(x=>o[x=~-x/n|0]=-~o[x],o=[])&&o].map(n=>~~n)

Попробуйте онлайн!

Или просто 43 байта / O (len (a)), если разрешены пустые элементы.

Arnauld
источник
[...o].map(n=>n|0)получает первый вывод из второго решения в меньшем количестве байтов.
Нил
@Neil Не уверен, почему я пошел на что-то такое замысловатое. : - /
Арно
2

Haskell , 63 75 70 байт

l!n=l#[n,2*n..]
[]#_=[]
l#(b:i)|h<-length$takeWhile(<=b)l=h:drop h l#i

Упс, этот короткий не линейный, а квадратичный; 

l!n=l#[n,2*n..]
[]#_=[]
l#(b:i)=sum[1|a<-l,a<=b]:[a|a<-l,a>b]#i

Попробуйте онлайн!

Angs
источник
1

Pyth, 23 22 байта

Jm/tdeQhQK*]ZheJhXRK1J

Попробуй здесь

Jm/tdeQhQK*]ZheJhXRK1J
Jm/tdeQhQ                 Find the bin for each time and save them as J.
         K*]ZheJ          Create empty bins.
                 XRK1J    Increment the bins for each time within them.
                h         Take the first (because mapping returned copies).

источник
1

Рубин , 53 50 байт

Редактировать: -3 байта от iamnotmaynard.

->a,b{(0..~-a.max/b).map{|i|a.count{|x|~-x/b==i}}}

Попробуйте онлайн!

Кирилл Л.
источник
Это не работает, когда a.maxне кратно b(например, f[[1,1,1,2,7,10],3]=>, [4, 0, 1]но должно дать [4, 0, 2]). Я попробовал тот же подход.
Восстановить Монику - Нотмайнард
(или, скорее [4, 0, 1, 1])
Восстановить Монику - notmaynard
Что ж, это можно исправить, переключившись на значение максимального диапазона с плавающей точкой, но я также попрошу OP уточнить это в описании задачи.
Кирилл Л.
50 байтов
Восстановить Монику - Нотмайнард
Хорошо, даже лучше, спасибо.
Кирилл Л.
1

Эта головоломка по сути является графом-сортировкой. Мы не знаем длину вывода, не пройдя сначала ввод.

C (лязг) , 53 байта

i,j;f(*A,l,b,*O){for(j=0;j<l;O[(A[j++]+b-1)/b-1]++);}

Попробуйте онлайн!

Это решение принимает следующие параметры: длина
Aвходного массива хранилища bin_size для вывода. Должен быть достаточной длины и возвращает результат в O.
l
b
O

Это решение имеет недостаток: оно не возвращает длину выходного массива O, и поэтому вызывающая сторона не знает, сколько печатать.

Следующая версия преодолевает этот недостаток:

C (лязг) , 79 байтов

i,j,k;f(*A,l,b,*O,*m){for(k=j=0;j<l;O[i=(A[j++]+b-1)/b-1]++,k=k>i?k:i);*m=++k;}

Попробуйте онлайн!

Он принимает дополнительный параметр mи возвращает в нем длину O. Это стоило мне 26 байт.

GPS
источник
1

C (gcc) , 102 90 89 86 байт

#define P!printf("%d ",k)
i,j,k;f(s){for(i=s;~scanf("%d",&j);k++)for(;j>i;i+=s)k=P;P;}

Попробуйте онлайн!

Спасибо Кевину Круйссену за сокращение 12 байт и потолочную кошку за еще 4 байта!

Г. Слипен
источник
1
90 байтов , используя for-loop, удаляя intи изменяя ==1на >0.
Кевин Круйссен,
Пожалуйста. Кстати, просто примечание, в настоящее время он недействителен (так же, как мой теперь удаленный ответ Java был). Он должен быть запущен O(n)вовремя, поэтому у вас не может быть вложенных циклов for (хотя ваш ответ на C ++ кажется нормальным. Поэтому я
добавил +1 к нему
Это все еще O (n). Внутренний цикл всегда будет печатать значение, и мы будем печатать только (максимальное значение + 1) / общее значение.
Г. Слипен
Хм, но уже не внешний цикл O(n)зацикливает входные элементы. Даже если внутренний цикл будет повторяться только 2 раза, он уже выше O(n). Или я что-то недопонимаю ... Должен признать, Oчто на самом деле это не моя компетенция ...
Кевин Круйссен
1
Но внутренний цикл не повторяется по всем входным элементам, он только повторяет по всем выходным значениям, которые необходимо напечатать, чтобы «догнать» позицию, соответствующую последнему входному элементу. Если входной вектор состоит из множества дубликатов или значений, которые отличаются меньше размера ячейки, внутренний цикл вообще не будет выполнять никаких итераций. С другой стороны, если входной вектор очень разреженный, то внутренний цикл будет выполнять больше итераций, печатая 0. Таким образом, чтобы быть правильным, код выполняется за O ((количество входных элементов) + (последний элемент / размер бина)). Это все еще линейно.
Г. Слипен