Struttura efficiente dei dati per implementare il file system falso

Question

Struttura efficiente dei dati per implementare il file system falso

#1 da (2 voti)

6

Voglio implementare una struttura dati che manterrà i percorsi delle directory, una sorta di file system falso.

Input: - Ho un file di configurazione del testo che contiene i percorsi come segue ...
C: / temp1
C: / temp1 / insideTemp1
C: / temp2 /
...

Potrei finire per immagazzinare enormi quantità di percorsi all'interno della struttura dati e sto cercando un periodo di prova molto basso.

Ecco le strutture dati che ritengo possano essere utili in questa situazione: -
Albero B
B + albero
Albero Wavelet
Trie
e B-Trie

Non sono sicuro di quale struttura dei dati sarebbe più utile in questa situazione. Non ho familiarità con B-trie, né ci sono molte risorse su Internet che posso trovare che mi aiuterebbero nell'implementazione e nella comprensione di una, ma penso che questa potrebbe essere una buona scelta per l'implementazione considerando che avrebbe vantaggi sia b tree and trie, correggimi se sbaglio. Mi piacerebbe sapere quale sarebbe la buona struttura dati nell'implementazione di questo problema e se è possibile reindirizzare alcune risorse che mi aiuterebbero a iniziare sarebbe bello! Inoltre, solo per curiosità, in futuro, se voglio espandere la struttura dei dati suggerita verso un sistema di file completo, la struttura dei dati suggerita dovrebbe essere sufficiente per espandere?

Ogni risposta è apprezzata.

data-structures file-systems trie

posta user3054204 11.07.2015 - 00:14

fonte

1 risposta

Leggi altre domande sui tag data-structures file-systems trie

Confronto di due stringhe grandi per vedere quanto corrispondono [duplicate] In che modo la ricerca elastica si avvicina al problema dell'appartenenza e del consenso distribuiti?

score 2 · Answer 1

Risposta rapida breve

Scegli prima una struttura ad albero normale, successivamente cerca una versione ottimizzata simile

Risposta estesa lunga e noiosa

Utilizza prima una struttura ad albero normale.

Ho letto che sembra che tu tenti di memorizzare l'intero percorso in ogni elemento del nodo, e questo è uno dei motivi per cui la tua struttura potrebbe richiedere un'ottimizzazione non necessaria.

Nota: i seguenti esempi sono pseudocodici. Questi non sono specifici linguaggi di programmazione, esempi finiti.

Invece di avere qualcosa di simile:

public struct NodeStruct
{
  public string FullPath;
  public *NodeStruct Container;
  public List<*NodeStruct> Items;
}

int main()
{
  int ErrorCode = 0;

  *NodeStruct MyFileSystem =
    new nodeStruct;
  MyFileSystem->FullPath = "FileSystem";
  MyFileSystem->Container = null;

  *NodeStruct CDrive =         
    new nodeStruct;
  CDrive->FullPath = "C:\";
  CDrive->Container = MyFileSystem;

  *NodeStruct DDrive =         
    new nodeStruct;
  DDrive->FullPath = "D:\";
  DDrive->Container = MyFileSystem;

  *NodeStruct SomeFolder = null;
  *NodeStruct SomeFile = null;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "C:\Program Files";
  SomeFolder->Container = CFolder;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "C:\My Documents";
  SomeFolder->Container = CFolder;

  SomeFile =
    new nodeStruct;
  MyFileSystem->FullPath = "C:\My Documents\Homework1.doc";
  MyFileSystem->Container = SomeFolder;

  free MyFileSystem;

  return ErrorCode;
} // int main(...)

Potresti volere qualcosa di simile a questo:

public struct NodeStruct
{
  string Identifier;

  public *NodeStruct Container;
  public List<*NodeStruct> Items;
}

string GetFullPath(*NodeStruct AFileSystemItem)
{
  string ErrorCode = "";

  // code to "traverse" a tree item or tree node
  // and get the full path

  return ErrorCode;
} // string GetFullPath(...)


int main()
{
  int ErrorCode = 0;

  *NodeStruct MyFileSystem =
    new nodeStruct;
  MyFileSystem->FullPath = "FileSystem";
  MyFileSystem->Container = null;

  *NodeStruct CDrive =         
    new nodeStruct;
  CDrive->FullPath = "C:";
  CDrive->Container = MyFileSystem;

  *NodeStruct DDrive =         
    new nodeStruct;
  DDrive->FullPath = "D:";
  DDrive->Container = MyFileSystem;

  *NodeStruct SomeFolder = null;
  *NodeStruct SomeFile = null;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "Program Files";
  SomeFolder->Container = CFolder;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "My Documents";
  SomeFolder->Container = CFolder;

  SomeFile =
    new nodeStruct;
  MyFileSystem->FullPath = "Homework1.doc";
  MyFileSystem->Container = SomeFolder;

  string AFullPath = GetFullPath(SomeFile);

  // "AFullPath" should have the "C:\My Documents\Homework1.doc" value

  free MyFileSystem;

  return ErrorCode;
} // int main(...)

Non hai specificato una particolare lingua di programmazione nella tua domanda. Né se utilizzi una P.L. imperativa, procedurale, funzionale o orientata agli oggetti, ciò potrebbe aiutarti a suggerirti una libreria.

Saluti.