Binning w czasie

12

Zadaniem w tym wyzwaniu jest umieszczenie elementów tablicy w przedziałach czasowych. Dane wejściowe będą stanowić nie malejącą tablicę dodatnich liczb całkowitych reprezentujących czas zdarzeń oraz liczbę całkowitą reprezentującą rozmiar każdego przedziału. Zacznijmy od przykładu. Nazywamy tablicę wejściową Ai tablicę wyjściową O.

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

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

Dlaczego ? Za pomocą a bin_size = 2mamy następujące przedziały:, w (0,2], (2,4], (4,6], (6,8], (8,10]których cztery elementy (1,1,1,2)znajdują się w pierwszym przedziale (0,2], żaden w drugim i trzecim przedziale, jeden 7w przedziale (6,8]i jeden 10w przedziale (8,10].

Twój kod powinien uwzględniać każdy przedział długości, bin_sizezaczynając od, 0i liczyć, ile jest w Anim liczb . Zawsze powinieneś umieszczać prawy koniec przedziału w pojemniku, więc w powyższym przykładzie 2jest on uwzględniony w liczbie 4. Twój kod powinien działać w czasie liniowym jako suma długości danych wejściowych i wyjściowych.

Więcej przykładów:

`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]`.

Możesz założyć, że dane wejściowe i wyjściowe można podawać w dowolnym dogodnym dla siebie formacie. Możesz używać dowolnych języków i bibliotek.

code-golf restricted-complexity
źródło
Czy 0dozwolone są wyjścia ze znakami końcowymi ? Więc wracasz [2,0,1,1,1,0]zamiast [2,0,1,1,1]?
Kevin Cruijssen
Proszę nie wstawiać zer.
2
Co z sytuacjami, w których maksymalna wartość tablicy nie jest wielokrotnością bin_size, czy naprawdę powinniśmy sobie z tym poradzić? Wydaje się, że większość odpowiedzi tak, ale jeśli tak, dobrze byłoby dodać przypadek testowy dla tego scenariusza, aby zapobiec nieporozumieniom.
Kirill L.
@KirillL. Tak, należy się z nimi obchodzić.
1
@GPS 0 nie jest dodatnią liczbą całkowitą. To nie jest przypadek :)

Odpowiedzi:

9

R , 48 bajtów

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

Wypróbuj online!

Jeszcze raz tablei cutzadzwoń do factorsztuczki na binowanie. Wypisuje nazwaną, vectorgdzie namessą przedziały, na przykład w notacji przedziałowej (0,5].

EDYCJA: Przywróć wcześniejszą wersję, która działa, gdy snie dzieli n.

Giuseppe
źródło
Naprawdę nie R, ale na TIO wydaje się, że generuje to format you [most likely do not] find convenientbez tableczęści.
mój zaimek to monicareinstate 30.03.18
@ ktoś, właśnie dlatego tam jest. cutdzieli wektor na czynniki o poziomach podanych w interwałach i tablezlicza wystąpienia każdej unikalnej wartości na wejściu.
Giuseppe
1
@ ktoś, ah, rozumiem, źle zrozumiałem twój komentarz. Nie, myślę, że to nie byłoby poprawne, ponieważ potrzebujemy liczby każdego pojemnika.
Giuseppe
1
Nie w pełni przetestowane, ale myślę, że można zaoszczędzić kilka bajtów reaplacing 0:ceiling(max(n)/s)*sz seq(0,max(n)+s-1,s). Działa przynajmniej dla dwóch próbek w pytaniu.
Gregor Thomas
1
@Gregor Hmm, jeśli to działa, 1:max(n/s+1)*s-sto kolejne ulepszenie, ponieważ oba są równoważne
Giuseppe
6

Oktawa , 36 bajtów

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

Wypróbuj online!

Polowanie na pisanki i rozpalanie ogniska. Dodam wyjaśnienie, kiedy będę miał czas.

Stewie Griffin
źródło
3

Perl 5 -a -i , 32 28 bajtów

Podaj liczbę po opcji -i. Daj każdy element wejściowy w osobnej linii na STDIN

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

Wypróbuj online!

Ton Hospel
źródło
2
To imponujące.
3

Python 2 , 62 bajty

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

Wypróbuj online!

Dead Possum
źródło
1
Po pierwsze: ładna odpowiedź, już ją dodałem + 1 (i utworzyłem port w Javie, ponieważ jest nieco krótszy niż to, co miałem). Końcowe zera nie są jednak dozwolone (tylko zapytał OP), więc I[-1]/s+1powinno być ~-I[-1]/s+1zamiast.
Kevin Cruijssen
@KevinCruijssen Dzięki za powiadomienie!
Dead Possum
3

05AB1E , 18 bajtów

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

Wypróbuj online!

Emigna
źródło
Nie znam tak dobrze 05AB1E, ale wydaje się, że wywołuje to A.count max (A) , więc czas działania nie jest liniowy w len (A) + len (O) . Czy to prawda, czy coś nie tak?
Dennis
@ Liczba Dennisa byłaby O(max(A)*max(A))... więc jest kwadratowa względem maksimum A ... OP określonego, że musi być liniowa pod względem ... co dokładnie?
Magic Octopus Urn
2
@MagicOctopusUrn Twój kod powinien działać w czasie liniowym jako suma długości danych wejściowych i wyjściowych , zgodnie z najnowszą wersją.
Dennis
2
@Dennis wydaje się to raczej arbitralne.
Magic Octopus Urn
2
@MagicOctopusUrn To chyba jedyna sensowna definicja liniowego czasu dla tego pytania.
2

APL + WIN, 23 bajty

Monity o wprowadzenie ekranów pojemników, a następnie wektora liczb całkowitych:

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

Wyjaśnienie:

⎕ 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
Graham
źródło
2

Java 8, 75 bajtów

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

Port odpowiedzi na Python 2 w DeadPossum , więc pamiętaj, aby głosować na jego odpowiedź!

Wyjaśnienie:

Wypróbuj online.

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
Kevin Cruijssen
źródło
2

JavaScript (ES6), 60 bajtów / O (len (a) + max (a) / n)

Zaoszczędź 5 bajtów dzięki @Neil

Pobiera dane wejściowe w składni curry (a)(n).

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

Wypróbuj online!

Lub tylko 43 bajty / O (len (a)), jeśli dozwolone są puste elementy.

Arnauld
źródło
[...o].map(n=>n|0)pobiera pierwsze wyjście z drugiego rozwiązania w mniejszej liczbie bajtów.
Neil
@Neil Nie jestem pewien, dlaczego wybrałem coś tak skomplikowanego. : - /
Arnauld
2

Haskell , 63 75 70 bajtów

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

Ups, ten krótszy nie jest liniowy, lecz kwadratowy; 

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

Wypróbuj online!

Angs
źródło
1

Pyth, 23 22 bajtów

Jm/tdeQhQK*]ZheJhXRK1J

Wypróbuj tutaj

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).

źródło
1

Rubin , 53 50 bajtów

Edycja: -3 bajty przez iamnotmaynard.

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

Wypróbuj online!

Kirill L.
źródło
To nie działa, gdy a.maxnie jest wielokrotnością b(np. f[[1,1,1,2,7,10],3]=>, [4, 0, 1]Ale powinno dać [4, 0, 2]). Próbowałem tego samego podejścia.
Przywróć Monikę - notmaynard
(a raczej [4, 0, 1, 1])
Przywróć Monikę - notmaynard
Cóż, można to naprawić, przełączając się na wartość maksymalnego zakresu zmiennoprzecinkowego, ale poproszę również OP o wyjaśnienie tego w opisie zadania.
Kirill L.
50 bajtów
Przywróć Monikę - notmaynard
Fajnie, jeszcze lepiej, dzięki.
Kirill L.
1

Ta łamigłówka to w zasadzie Count-sort. Nie znamy długości wyjścia bez uprzedniego przejrzenia danych wejściowych.

C (brzęk) , 53 bajty

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

Wypróbuj online!

To rozwiązanie przyjmuje następujące parametry: długość
Atablicy wejściowej pamięci bin_size dla Output. Musi mieć wystarczającą długość
l
b
O
i zwraca wynik w O.

To rozwiązanie ma utrudnienie: nie zwraca długości tablicy wyjściowej O, więc osoba dzwoniąca nie wie, ile wydrukować.

Poniższa wersja pokonuje ten utrudnienie:

C (brzęk) , 79 bajtów

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;}

Wypróbuj online!

Wymaga dodatkowego parametru m i zwraca Ow nim długość . Kosztowało mnie 26 bajtów.

GPS
źródło
1

C (gcc) , 102 90 89 86 bajtów

#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;}

Wypróbuj online!

Podziękowania dla Kevina Cruijssena za wykrawanie 12 bajtów, a dla kota sufitowego za kolejne 4 bajty!

G. Sliepen
źródło
1
90 bajtów przy użyciu pętli for, usuwając inti zmieniając ==1na >0.
Kevin Cruijssen
Nie ma za co. Przy okazji, tylko uwaga, jest obecnie nieprawidłowa (tak jak moja teraz usunięta odpowiedź Java). Musi działać w O(n)czasie, więc nie możesz mieć żadnych zagnieżdżonych pętli for. (Twoja odpowiedź w C ++ wydaje się być w porządku. Więc mam +1 + ed. :))
Kevin Cruijssen
Nadal jest to O (n). Wewnętrzna pętla zawsze drukuje wartość, a my drukujemy tylko (wartość maksymalna + 1) / wartości binsize ogółem.
G. Sliepen
Hmm, ale nie jest to już zewnętrzna pętla O(n)przez zapętlenie elementów wejściowych. Nawet jeśli wewnętrzna pętla zapętliby się tylko 2 razy, to już jest powyżej O(n). A może coś źle zrozumiałem ... Muszę przyznać, że Oczasy nie są tak naprawdę moją wiedzą ...
Kevin Cruijssen
1
Ale wewnętrzna pętla nie wykonuje iteracji po wszystkich elementach wejściowych, tylko iteruje po wielu wartościach wyjściowych, które musi wydrukować, aby „dogonić” pozycję odpowiadającą najnowszemu elementowi wejściowemu. Jeśli wektor wejściowy składa się z wielu duplikatów lub wartości, które różnią się mniej niż rozmiar pojemnika, wewnętrzna pętla w ogóle nie wykona żadnych iteracji. Z drugiej strony, jeśli wektor wejściowy jest bardzo rzadki, wówczas wewnętrzna pętla wykona więcej iteracji, wypisując zera. Aby być poprawnym, kod działa w czasie O ((liczba elementów wejściowych) + (rozmiar ostatniego elementu / bin). To wciąż jest liniowe.
G. Sliepen