Algoritmo para determinar transacciones entre series de datos semanales?

9

Estoy tratando de desarrollar una pequeña herramienta de informes (con sqlite backend). Puedo describir mejor esta herramienta como un libro de contabilidad de "transacciones". Lo que intento hacer es realizar un seguimiento de las "transacciones" del extracto de datos semanal:

  • "nuevo" (o agregar): el recurso es nuevo para mi aplicación, ya que es posible que mi aplicación no haya rastreado este recurso antes, ya que no se ha visto a través de extractos.
  • "actualizar" (o hit): hay un uso reciente de ese recurso, actualizar el período de retención por otra semana.
  • "eliminar" (o soltar): este elemento no se utilizó desde el último informe (opcional, pero sería bueno tenerlo para representar gráficamente los cambios semanales en la demanda de recursos).

Todo lo que tengo es un extracto de datos semanal (archivo plano delimitado por tuberías) que proviene de un sistema de archivo / gestión de registros heredado sobre el que no tengo control.

Cada línea se puede destilar básicamente a esto:
resource_id | resource info | customer_id | customer_info

Data de muestra:

10| Title X       | 1 | Bob
11| Another title | 1 | Bob
10| Title X       | 2 | Alice

El objetivo es facilitar la presentación de informes sobre los recursos que no se han utilizado durante X meses (según el último resultado). Hay un período de retención donde los recursos se mantienen para facilitar el acceso si son populares. Un recurso que no se ha usado durante 18 meses está marcado para el archivo a largo plazo en otros lugares.

Esto debe ser un problema común. ¿Se pregunta si existe un algoritmo de propósito general para determinar qué hay de nuevo / igual / eliminado entre los conjuntos de datos (DB vs. último extracto)?

Swartz
fuente

Respuestas:

1

Bueno, tu respuesta es ... Sí. Hay un algoritmo simple que puede implementar que no requiere ninguna de esas otras cosas. Es un algoritmo de valor presente neto. Es fácil de implementar y todo lo que requiere en el extremo de la base de datos es que marque con fecha los datos semanales y escriba una consulta simple y una pequeña función recursiva o for loop, o podría hacer una de esas otras soluciones.

NPV = PV- (PV (CP / T) o el nuevo valor presente es igual al valor presente multiplicado por el período actual (meses desde la última entrada) dividido por el término (por ejemplo, 18 meses) cuando el valor del recurso cae a 0 es el valor presente neto se gasta

Si me das un idioma en el que lo quieres, publicaré el código aquí en una edición

J-Boss
fuente
El idioma no es tan importante. Ruby o C ++ si tuviera que elegir. Si puedes escribir un algoritmo en HTML 4.0 Strict, serás mi héroe. Bromeando sobre esa última parte :)
Swartz
Estaría interesado en ver el código. Ruby o C ++. Gracias.
Swartz
0

Si mantiene las actualizaciones en un servidor SQLite de todos modos, podría convertir la actualización semanal en una nueva tabla y compararla con los datos archivados con consultas, antes de fusionarla.

Ejemplo de uso de SQL para encontrar nuevas adiciones a una tabla: /programming/2077807/sql-query-to-return-differences-between-two-tables

Si un campo en su base de datos almacena la fecha de la transacción, puede consultar a todos los usuarios que han realizado transacciones en los últimos 18 meses. Entonces el archivo es solo el DB completo. Alternativamente, puede consultar a todos los usuarios que no lo hayan hecho, extraer sus datos y luego soltarlos. Las actualizaciones son solo las filas marcadas con el tiempo esta semana.

Davislor
fuente
Mejor, es una solución centrada en los datos al menos, pero todavía es exagerada
J-Boss
Estoy usando un sqlite por el momento, ya que es fácil comenzar. Podría cambiar fácilmente a MySQL (o PostgreSQL). Si el uso de un back-end que no sea SQL generaría algo para que esto funcione aún mejor, soy todo oídos.
Swartz
Bueno, mi pensamiento era principalmente que lo estás convirtiendo en filas en una base de datos de todos modos . Si no necesita ejecutarlo desde múltiples procesos al mismo tiempo, no creo que quiera cambiar a algo más pesado que SQLite.
Davislor
No hay necesidad de procesamiento concurrente. Pero necesito almacenar los datos sobre recursos en alguna parte. Una base de datos SQL parecía una buena opción. Sin embargo, no hay nada que me impida cargar datos en cualquier tipo de datos para procesar deltas. Todo lo que quiero al final de cada ejecución de extracto es descubrir qué hay de nuevo, qué permaneció igual y qué ha desaparecido. Puedo averiguar cómo actualizar los registros según sea necesario a partir de esta información.
Swartz
Después de analizar los datos y ponerlos en la base de datos, probablemente sea más sencillo escribir una consulta que implementar un algoritmo. Dicho esto, si desea codificarlo, el algoritmo que desea establece la diferencia y hay una implementación en C ++ STL que puede usar para hacerlo en una sola línea una vez que haya colocado ambos conjuntos de datos en el contenedor de tu elección, probablemente a Vector.
Davislor
0

Idea alternativa:

  1. Analice su lista de transacciones en algún tipo de estructura de datos, como una matriz. (En C ++, piense Vector, y en Java,. ArrayList)

  2. Realizar una consulta en SQL backend como SELECT DISTINCT customer_id FROM Transactions ORDER BY customer_idy el paquete de ID de cliente ordenados diferentes en un conjunto, old. Si hace exactamente lo mismo con una WHEREcláusula que separa las transacciones antiguas y nuevas, puede omitir el paso 3.

  3. Obtenga los ID de clientes únicos de las nuevas actualizaciones en una estructura de datos separada, en orden ordenado. Hay un par de estructuras de datos que puede utilizar para obtener es en una estructura de datos, new. La ordenación por inserción en una lista de doble enlace es muy simple, pero usar una tabla hash intermedia se ejecutaría en un tiempo cercano al lineal, o si está ordenando la matriz original de todos modos, obtener un conjunto de eso es fácil.

  4. Tome la diferencia establecida new: olduse la biblioteca estándar de su idioma favorito. ¿Tu idioma favorito tiene este algoritmo en su biblioteca estándar?

Las otras cosas que desea hacer son definitivamente consultas SQL después de haber actualizado su base de datos de transacciones.

Nota sobre el paso 3: considere la naturaleza de sus datos. Suponga que su archivo de texto enumera los pedidos cronológicamente, y en una semana típica, hay muchos clientes nuevos que reciben un nuevo customer_iden orden ascendente. Suponga que la mayoría de los otros pedidos provienen de un pequeño número de clientes leales que repiten, con menor customer_id. Entonces sus entradas ya están clasificadas en su mayoría. Un tipo de inserción en el que intente insertar bajo customer_iden la parte delantera de una lista de doble enlace y alto customer_iden la parte posterior, en esa situación, funcionaría bien en la práctica.

Davislor
fuente
1
Estoy más interesado en los recursos nuevos / iguales / actualizados que en los clientes. Pero sí, la idea sería la misma.
Swartz
0

Según tengo entendido por su pregunta, en realidad tiene resource_id (+ info) y "lista" de clientes (id + info).

Por lo tanto, puede mantener fácilmente la Lista de clientes por recurso y verificar el último nodo en cada lista del recurso (para saber el último tiempo de operación; solo necesita agregar el campo de fecha a su cliente en el código)

No estoy familiarizado con SQL, por lo tanto, doy mi ejemplo con HashMapList, pero estoy seguro de que es la misma idea: HashMap <Resource, List<Customer>>cuándo Resourcedebe contener resourceID como clave y Customerdebe contener ID de cliente, información y fecha de operación.

Con esta idea, puede conocer fácilmente el último tiempo de operación y puede modificar cualquier recurso (agregar \ eliminar recurso \ cliente).

AsfK
fuente
0

Si está utilizando una base de datos SqLite, si agrega la fecha del lote también como una columna de la tabla,

10| Title X       | 1 | Bob    | 2015-03-01
11| Another title | 1 | Bob    | 2015-03-01
...............................
10| Title X       | 1 | Alice  | 2015-03-05

sería bastante fácil usar un SQL para obtener los recursos que no se usaron en los últimos X días

Select distinct r.ResourceID from Resources r
where not exists (SELECT julianday('now') - julianday(r.DateUpdated)) < X

No he probado el SQL pero debería darte una idea

Pelican de bajo vuelo
fuente
0

De la publicación original, parece que los datos que se ingieren no tienen un campo para indicar la fecha / hora de la transacción, y supongo que el archivo se ingiere con frecuencia en un horario tal como diario, por hora, etc.

Manejaría esto agregando una columna de marca de tiempo de SQL que se genera automáticamente en el nivel de la base de datos o mediante el código que extrae los datos y los inserta en la base de datos. Luego pones un índice en esa columna de marca de tiempo y terminas con ella. Deje que el motor de base de datos haga el trabajo de hacer que sea eficiente responder la pregunta "cuántas transacciones no han ocurrido desde este momento" o "cuántas entre este momento y ese momento".

Luego, programa un trabajo para consultar y calcular los diferenciales sobre los que desea informar. Las transacciones que son "nuevas" son transacciones que no tienen ningún registro en la base de datos antes de la fecha en que se solicita "nuevo desde". Los registros antiguos son aquellos que no tienen transacciones desde una fecha de corte.

Thomas Carlisle
fuente
-2

¿No es esto para lo que son las HashTables? Si todo lo que desea hacer es mantener registros de los recursos que se han utilizado en los últimos meses y eliminar los recursos a los que no se ha accedido en los últimos 18 meses, puede usar una tabla de hash donde la clave es el resource_id y el valor es el última fecha de acceso.

Para archivar los registros> 18 meses, puede revisar todos los registros en la tabla hash y simplemente eliminar (o mover) esos registros específicos. (puede hacer esto semanalmente cuando llegue el informe)

Adrian Buzea
fuente
¿Por qué la necesidad de HashTable si estoy almacenando cosas en la base de datos? Puedo hacer actualizaciones a los registros db. Estoy más interesado en un caso: tome dos conjuntos de datos, descubra las diferencias (lo que se agrega, sigue siendo el mismo, se elimina) entre los dos conjuntos. ¿Cómo ayudaría una técnica HashTable a encontrar registros nuevos y "eliminados"?
Swartz
Si las tablas están indexadas en la base de datos, entonces básicamente también son HashTables detrás de escena. Si tiene 2 tablas, cada una de las cuales representa un conjunto de datos, puede obtener sus registros nuevos y eliminados haciendo algunas uniones externas. Consulte esto como referencia: i.stack.imgur.com/pxUO3.png . Asegúrese de tener índices en la columna resource_id y debería ser bastante rápido. Si tuviera que implementar esto desde cero, entonces creo que HashTables aún sería el camino a seguir, ya que puede hacer búsquedas / inserciones / supresiones en O (1) tiempo amortizado. No puedo pensar en una forma más eficiente de hacer esto.
Adrian Buzea
3
Hay mejores estructuras de datos que manejan el envejecimiento sin los pasos adicionales de meter esto en una tabla hash.
¿Quieres mencionar algunos?
Adrian Buzea
@Snowman - Ojalá pudiera aumentar eso un par de veces más, solo estaré totalmente de acuerdo en este comentario
J-Boss