Binning en el tiempo

12

La tarea en este desafío es colocar elementos de una matriz en contenedores de tiempo. La entrada será una matriz no decreciente de enteros positivos que representan el tiempo de los eventos, y un entero que representa el tamaño de cada bin. Comencemos con un ejemplo. Llamamos a la matriz de entrada Ay a la matriz de salida O.

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

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

¿Por qué ? Con a bin_size = 2, tendremos los siguientes intervalos: (0,2], (2,4], (4,6], (6,8], (8,10]donde cuatro elementos (1,1,1,2)están dentro del primer intervalo (0,2], ninguno en el segundo y tercer intervalo, uno 7en el intervalo (6,8]y uno 10en el intervalo (8,10].

Su código debe considerar cada intervalo de longitud a bin_sizepartir de 0y contar cuántos números Ahay en cada uno. Siempre debe incluir el extremo derecho de un intervalo en un contenedor para que en el ejemplo anterior 2se incluya en el recuento de 4. Su código debe ejecutarse en tiempo lineal en la suma de las longitudes de la entrada y la salida.

Más ejemplos:

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

Puede suponer que la entrada y la salida se pueden dar en cualquier formato que considere conveniente. Puede usar cualquier idioma y biblioteca que desee.

code-golf restricted-complexity
fuente
¿Están 0permitidas las salidas con trailing s? ¿Entonces regresar en [2,0,1,1,1,0]lugar de [2,0,1,1,1]?
Kevin Cruijssen
No ceros a la derecha por favor.
2
¿Qué pasa con las situaciones en las que el valor máximo de la matriz no es un múltiplo de bin_size? Parece que la mayoría de las respuestas sí, pero si es así, sería bueno agregar un caso de prueba para este escenario para evitar confusiones.
Kirill L.
@KirillL. Sí, también deberían ser manejados.
1
@GPS 0 no es un entero positivo. Esto no es un accidente :)

Respuestas:

9

R , 48 bytes

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

Pruébalo en línea!

Una vez más, tabley haciendo cutun factortruco para el binning. Emite un nombre vectordonde namesestán los intervalos, en notación de intervalo, por ejemplo (0,5].

EDITAR: vuelva a la versión anterior que funciona cuando sno se divide n.

Giuseppe
fuente
Realmente no tengo R, pero en TIO parece que sale un format you [most likely do not] find convenientsin la tableparte.
mi pronombre es monicareinstate
@ alguien es exactamente por eso que está ahí. cutdivide el vector en factores con niveles dados por los intervalos y tablecuenta las ocurrencias de cada valor único en su entrada.
Giuseppe
1
@ alguien ah, ya veo, entendí mal tu comentario. No, creo que eso no sería válido ya que necesitamos los recuentos de cada contenedor.
Giuseppe
1
No está completamente probado, pero creo que se puede ahorrar un par bytes reaplacing 0:ceiling(max(n)/s)*scon seq(0,max(n)+s-1,s). Funciona al menos para las dos muestras en la pregunta.
Gregor Thomas
1
@Gregor Hmm si eso funciona 1:max(n/s+1)*s-ses otra mejora ya que los dos son equivalentes
Giuseppe
6

Octava , 36 bytes

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

Pruébalo en línea!

Cazando huevos de Pascua y haciendo una hoguera. Agregaré una explicación cuando tenga tiempo.

Stewie Griffin
fuente
3

Perl 5 -a -i , 32 28 bytes

Dar cuenta después de la opción -i. Dé a cada elemento de entrada en una línea separada en STDIN

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

Pruébalo en línea!

Ton Hospel
fuente
2
Esto es impresionante
3

Python 2 , 62 bytes

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

Pruébalo en línea!

Zarigüeya muerta
fuente
1
En primer lugar: buena respuesta, ya lo hice + 1-ed (y creé un puerto en Java, porque es bastante más corto de lo que tenía). Sin embargo, los ceros finales no están permitidos (solo se le preguntó a OP), por lo que I[-1]/s+1deberían estarlo ~-I[-1]/s+1.
Kevin Cruijssen
@KevinCruijssen Gracias por el aviso!
Dead Possum
3

05AB1E , 18 bytes

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

Pruébalo en línea!

Emigna
fuente
No conozco bien a 05AB1E, pero esto parece llamar a A.count max (A) , por lo que el tiempo de ejecución no es lineal en len (A) + len (O) . ¿Es correcto o me equivoqué?
Dennis
El recuento de @Dennis sería O(max(A)*max(A))... así que es cuadrático en el máximo de A ... OP especificó que tenía que ser lineal en términos de ... ¿qué exactamente?
Urna mágica de pulpo
2
@MagicOctopusUrn Su código debe ejecutarse en tiempo lineal en la suma de las longitudes de entrada y salida , de acuerdo con la última revisión.
Dennis
2
@Dennis que parece bastante arbitrario.
Urna mágica de pulpo
2
@MagicOctopusUrn Creo que es la única definición sensata de tiempo lineal para esta pregunta.
2

APL + WIN, 23 bytes

Solicita la entrada de pantalla de contenedores y luego el vector de enteros:

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

Explicación:

⎕ 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
fuente
2

Java 8, 75 bytes

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

Puerto de la respuesta Python 2 de @ DeadPossum , ¡así que asegúrese de votar su respuesta!

Explicación:

Pruébalo en línea.

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
fuente
2

JavaScript (ES6), 60 bytes / O (len (a) + max (a) / n)

Guardado 5 bytes gracias a @Neil

Toma entrada en la sintaxis de curry (a)(n).

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

Pruébalo en línea!

O solo 43 bytes / O (len (a)) si se permiten elementos vacíos.

Arnauld
fuente
[...o].map(n=>n|0)obtiene la primera salida de la segunda solución en menos bytes.
Neil
@Neil No estoy seguro de por qué fui por algo tan complicado. : - /
Arnauld
2

Haskell , 63 75 70 bytes

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

Vaya, este más corto no es lineal sino cuadrático; 

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

Pruébalo en línea!

Angs
fuente
1

Pyth, 23 22 bytes

Jm/tdeQhQK*]ZheJhXRK1J

Pruébalo aquí

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

fuente
1

Ruby , 53 50 bytes

Editar: -3 bytes por iamnotmaynard.

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

Pruébalo en línea!

Kirill L.
fuente
Esto no funciona cuando a.maxno es un múltiplo de b(por ejemplo, f[[1,1,1,2,7,10],3]=> [4, 0, 1]pero debería dar [4, 0, 2]). Había intentado el mismo enfoque.
Restablece a Monica - notmaynard el
(o mejor dicho [4, 0, 1, 1])
Restablece a Monica - notmaynard el
Bueno, esto se puede solucionar cambiando a un valor de rango máximo flotante, pero también le pediré a OP que aclare esto en la descripción de la tarea.
Kirill L.
50 bytes
Restablecer Monica - notmaynard
Agradable, incluso mejor, gracias.
Kirill L.
1

Este rompecabezas es esencialmente un tipo de conteo. No sabemos la longitud de salida sin pasar primero por la entrada.

C (clang) , 53 bytes

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

Pruébalo en línea!

Esta solución toma los siguientes parámetros: longitud de la
Amatriz de entrada
ldel almacenamiento A
bbin_size
Opara Salida. Debe tener una longitud suficiente
y devuelve la salida en O.

Esta solución tiene una desventaja: no devuelve la longitud de la matriz de salida O, por lo que la persona que llama no sabe cuánto imprimir.

La siguiente versión supera esa desventaja:

C (clang) , 79 bytes

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

Pruébalo en línea!

Toma un parámetro adicional my devuelve la longitud de Oeste. Me costó 26 bytes.

GPS
fuente
1

C (gcc) , 102 90 89 86 bytes

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

Pruébalo en línea!

¡Gracias a Kevin Cruijssen por recortar 12 bytes y a ceilingcat por otros 4 bytes!

G. Sliepen
fuente
1
90 bytes mediante el uso de bucles for, eliminando inty cambiando ==1a >0.
Kevin Cruijssen
De nada. Por cierto, solo una nota, actualmente no es válido (al igual que mi respuesta Java ahora eliminada). Es necesario para ejecutar en el O(n)tiempo, por lo que no puede tener ningún anidarse para-bucles .. (C ++ Su respuesta parece bien, aunque por lo que he + 1-ed que uno :)..)
Kevin Cruijssen
Todavía es O (n). El bucle interno siempre imprimirá un valor, y solo imprimiremos (valor máximo + 1) / binsize en total.
G. Sliepen
Hmm, pero ya no es el bucle externo al recorrer O(n)los elementos de entrada. Incluso si el bucle interno solo se repitiera 2 veces, ya está arriba O(n). O estoy mal entendido algo .. tengo que admitir O-los tiempos no son realmente mi experiencia ..
Kevin Cruijssen
1
Pero el bucle interno no itera sobre todos los elementos de entrada, solo itera sobre la cantidad de valores de salida que necesita imprimir para "ponerse al día" en la posición correspondiente al último elemento de entrada. Si el vector de entrada consta de muchos duplicados o valores que difieren menos que el tamaño del contenedor, el bucle interno no realizará ninguna iteración. Por otro lado, si el vector de entrada es muy escaso, el bucle interno realizará más iteraciones, imprimiendo ceros. Entonces, para ser correcto, el código se ejecuta en tiempo O ((número de elementos de entrada) + (último elemento / tamaño del contenedor)). Esto sigue siendo lineal.
G. Sliepen