Processo per generare una struttura gerarchica basata su dati relazionali?

6

Ho un csv di ID dei dipendenti, nomi e una colonna di riferimento con l'id del loro manager diretto, dì qualcosa del genere

 emp_id, emp_name, mgr_id
1,The Boss,,
2,Manager Joe,1
3,Manager Sally,1
4,Peon Frank,2
5,Peon Jill,2
6,Peon Rodger,3
7,Peon Ralph,3

Mi piacerebbe essere in grado di generare un oggetto (json) che rappresenta questa struttura, qualcosa sulla falsariga di

DATA = {
  "parent": "The Boss",
  "children: [
    {
      "parent": "Manager Joe",
      "children": [ {"parent": "Peon Frank"}, {"parent": "Peon Jill"} ]
    },
    {
      "parent": "Manager Sally",
      "children": [ {"parent": "Peon Rodger"}, {"parent": "Peon Ralph" } ]
    }]
}

Quindi dai dati, una voce senza mgr_id rappresenta qualcosa come l'amministratore delegato o il leader.

Quindi raccogli alcuni pensieri .. So che questo potrebbe essere rappresentato da una struttura di dati ad albero con l'attraversamento dell'albero che genera l'output corretto. Il parser dovrebbe essere responsabile per l'inserimento nell'albero. Forse il numero di bambini ti darebbe un peso? Solo raccogliendo pensieri. Non sono sicuro di come ruoterò attorno al fatto che più oggetti possono essere costruiti con i bambini.

Esiste un algoritmo definito in grado di analizzare questa struttura a cui non sto pensando? Discendere verso il basso nei bambini sembra relativamente semplice. Non vedo questo nella mia testa, e potrei usare un po 'd'aiuto. Grazie

    
posta darethas 27.10.2014 - 23:03
fonte

2 risposte

3

Ci sono diversi modi per creare una struttura dalla pianura La ricorsione è una delle migliori. Questo il programma lo usa, con una fase preliminare di figurazione quali elementi sono i genitori.

Mentre la strategia è indipendente dalla lingua, ogni lingua ha diversi dettagli delle strutture dati e costruzioni. Ho reso l'approccio in Python.

NB, circa la metà di questo codice è a scopo di visualizzazione e dimostrazione, quindi puoi seguire e vedere come funziona l'algoritmo. Per la produzione, tassa gratuita per rimuovere quelle parti.

Oh ... e ho cambiato le etichette da "padre" a "nome" e "bambini" a "rapporti" perché l'ho trovato più gradevole. Puoi, ovviamente, scegliere quello che vuoi.

from pprint import pprint
from random import shuffle
from collections import defaultdict
import json

def show_val(title, val):
    """
    Debugging print helpler.
    """
    sep = '-' * len(title)
    print "\n{0}\n{1}\n{2}\n".format(sep, title, sep)
    pprint(val)


# ORIGINAL NAMES:   emp_id, emp_name, mgr_id
# SIMPLIFIED NAMES: eid,    name,     mid
text = """
323,The Boss,
4444,Manager Joe,323
3,Manager Sally,323
4,Peon Frank,4444
33,Peon Dave,3
5,Peon Jill,4444
6,Peon Rodger,3
7,Peon Ralph,3
233,Clerk Jane,99
99,Supervisor Henri,3
"""

# parse text into lines
lines = [ l.strip() for l in text.strip().splitlines() ]

# construct list of people tuples
people = [ tuple(l.split(',')) for l in lines ]

# for demonstration and testing only, shuffle the results
shuffle(people)
show_val("randomized people", people)

# contstruct list of parents
parents = defaultdict(list)
for p in people:
    parents[p[2]].append(p)
show_val("parents", parents)

def buildtree(t=None, parent_eid=''):
    """
    Given a parents lookup structure, construct
    a data hierarchy.
    """
    parent = parents.get(parent_eid, None)
    if parent is None:
        return t
    for eid, name, mid in parent:
        report = { 'name': name }
        if t is None:
            t = report
        else:
            reports = t.setdefault('reports', [])
            reports.append(report)
        buildtree(report, eid)
    return t

data = buildtree()
show_val("data", data)

show_val("JSON", json.dumps(data))

In esecuzione questo mostra il seguente output:

-----------------
randomized people
-----------------

[('233', 'Clerk Jane', '99'),
 ('4444', 'Manager Joe', '323'),
 ('33', 'Peon Dave', '3'),
 ('6', 'Peon Rodger', '3'),
 ('99', 'Supervisor Henri', '3'),
 ('3', 'Manager Sally', '323'),
 ('5', 'Peon Jill', '4444'),
 ('323', 'The Boss', ''),
 ('4', 'Peon Frank', '4444'),
 ('7', 'Peon Ralph', '3')]

-------
parents
-------

defaultdict(<type 'list'>, {'99': [('233', 'Clerk Jane', '99')], '323': [('4444', 'Manager Joe', '323'), ('3', 'Manager Sally', '323')], '3': [('33', 'Peon Dave', '3'), ('6', 'Peon Rodger', '3'), ('99', 'Supervisor Henri', '3'), ('7', 'Peon Ralph', '3')], '4444': [('5', 'Peon Jill', '4444'), ('4', 'Peon Frank', '4444')], '': [('323', 'The Boss', '')]})

----
data
----

{'name': 'The Boss',
 'reports': [{'name': 'Manager Joe',
              'reports': [{'name': 'Peon Jill'}, {'name': 'Peon Frank'}]},
             {'name': 'Manager Sally',
              'reports': [{'name': 'Peon Dave'},
                          {'name': 'Peon Rodger'},
                          {'name': 'Supervisor Henri',
                           'reports': [{'name': 'Clerk Jane'}]},
                          {'name': 'Peon Ralph'}]}]}

----
JSON
----

'{"name": "The Boss", "reports": [{"name": "Manager Joe", "reports": [{"name": "Peon Jill"}, {"name": "Peon Frank"}]}, {"name": "Manager Sally", "reports": [{"name": "Peon Dave"}, {"name": "Peon Rodger"}, {"name": "Supervisor Henri", "reports": [{"name": "Clerk Jane"}]}, {"name": "Peon Ralph"}]}]}'

Alcuni preliminari: usa anche print per aiutare a mostrare i dati annidati strutture. Normalmente riceviamo dati attraverso un database connessione, qui solo la analizziamo dal testo statico. Infine, mentre i dati che hai presentato sono meravigliosamente ordinati, con il boss in alto e con i numeri di identificazione dei dipendenti più bassi (semplificando il) problema, vorrei confermare che il codice funziona in qualsiasi ordine. Quindi ho modificato alcuni dei numeri di identificazione per riflettere un'assegnazione non sequenziale e introdotti random.shuffle per randomizzare l'ordine dei dati. Non lo faresti in produzione, ma come parte della sperimentazione, aumenta la fiducia della logica lavorando in base alla progettazione, non a caso.

    
risposta data 28.10.2014 - 03:40
fonte
2

Hai un file CSV come forma di persistenza. Esistono altri approcci come SQLite che potresti voler indagare fornendoti un po 'più di capacità di interrogare la struttura, ma avrai comunque il problema che per costruire la struttura ad albero completa per la serializzazione, è necessario avere la struttura ad albero completa.

Lavorando con CSV, dovrai leggere ogni riga, costruire la struttura ad albero corrispondente e poi riscriverla, possibilmente con una libreria per la serializzazione json. Notando che hai alcuni bit rubino su SO, potrebbe sembrare qualcosa come le risposte in Oggetti ruby e serializzazione JSON (senza Rails) e per la lettura, la gemma CSV . Questo è solo un esempio, tuttavia, tali parser CSV e obiettivi di serializzazione JSON esistono per ogni lingua di valore pratico da remoto.

Ecco a cosa si riduce davvero. È possibile che tu possa avere qualcosa che assomigli:

1,The Boss,,
2,Founder Dev,7
3,Manager Joe,1
4,Peon Frank,3
5,Peon Jill,3
6,Peon Rodger,7
7,Manager Sally,1

E così, devi leggerlo all prima di poter creare il json per serializzarlo. Non c'è modo di aggirare questo.

Ora, c'è la possibilità di una diversa struttura nel csv che ti permetta di fare alcune query più utili e velocemente senza dover costruire la struttura a tre completa per poi lavorare con.

Il set innestato che può anche essere visto come un può essere utile.

L'albero ha questo aspetto:

                1 Boss 14                   

2 Manager Sally 7       8 Manager Joe 13     

3 Dev 4 | 5 Rodger 6    9 Frank 10 | 11 Jill 12

E il file corrispondente verrebbe scritto come:

# name  L   R
Boss,   1,  14
Sally,  2,  7
Dev,    3,  4
Rodger, 5,  6
Joe,    8,  13
Frank,  9,  10
Jill,   11, 12

Con questo albero, si possono fare cose come "trova tutti i manager" trovando tutte le linee dove R-L > 1 . Oppure, "trova tutti a riferire a Sally" trovando tutte le righe in cui L > 2 and R < 7 . Il numero di persone che riferiscono a una determinata persona è (R-L-1)/2 . Ciò consente di poter leggere le domande specifiche sull'albero molto più velocemente (senza dover costruire l'albero stesso).

L'albero dei preordini modificato viene fornito con la spesa che gli aggiornamenti toccheranno un numero elevato di righe rispetto alla lista di adiacenze approccio a un org albero. Un inserto sposterà i numeri in tutto il luogo. Ad esempio, se Sally aveva un'altra persona che le stava segnalando, quella persona avrebbe il valore 7,8 e avresti bisogno di modificare if(L > 7) L = L + 2 e if (R > 7) R = R + 2 di tutti.

    
risposta data 28.10.2014 - 02:56
fonte

Leggi altre domande sui tag