Implementazione di hash e array immutabile in JavaScript?

Question

È semplice l'implementazione di hash e array immutabile in javascript? Non ho bisogno della migliore velocità, una velocità ragionevole migliore di un clone sarebbe buono.

Inoltre, se ci sono semplici implementazioni in Java o altri linguaggi che possono essere facilmente comprensibile e portato a JavaScript, sarebbe anche bello.

UPDATE:

L'obiettivo è quello di non solo ha congelato l'hash (o array), ma per rendere un efficace attuazione di un'operazione di aggiornamento - aggiornamento hash immutabile dovrebbe restituire un nuovo hash immutabile. E dovrebbe essere più efficiente di farlo "clonare l'originale e aggiornarlo".

I tipi di JS nativi hanno complessità di aggiornamento qualcosa come O (1), con la clonazione la complessità sarà O (n), con strutture di dati immutabili speciali (quello che ho chiesto) sarà 0 (log (n))

UPDATE2: JavaScript ha già Array/Hash:

Sì, ma sono mutevoli, ho bisogno di qualcosa di simile, ma immutabile, in fondo si può essere fatto molto semplicemente clonazione hash2 = hash1.clone(); hash2[key] = value ma è molto inefficiente, ci sono algoritmi che lo hanno reso molto efficiente, senza utilizzare lo clone.

hash1 = {} 
hash2 = hash1.set('key', 'value2') 
hash3 = hash1.set('key', 'value3) 

console.log(hash1) // => {} 
console.log(hash2) // => {key: 'value2'} 
console.log(hash3) // => {key: 'value3'} 

SOLUZIONE:

Non è un'implementazione per hash immutabile, ma più come un hack per il mio problema attuale, forse aiuta anche qualcuno.

Un po 'di più sul perché ho bisogno di strutture di dati immutabili - Io uso Node.js e una sorta di database in memoria. Una richiesta può leggere il database, altri aggiornarlo - l'aggiornamento può richiedere molto tempo (chiamare i servizi remoti) - quindi non posso bloccare tutti i processi di lettura e attendere che l'aggiornamento sia terminato, anche l'aggiornamento potrebbe fallire e il database dovrebbe essere ripristinato . Quindi ho bisogno di isolare (ACID) in qualche modo le operazioni di lettura e scrittura sul database in memoria.

Ecco perché ho bisogno di matrici e hash immutabili - per implementare una sorta di MVCC. Ma sembra che ci sia un modo più semplice per farlo. Invece di aggiornare direttamente il database - l'operazione di aggiornamento registra solo le modifiche al database (ma non lo esegue direttamente) - in forma di "aggiungi 42 a array db.someArray".

Alla fine, il prodotto dell'operazione di aggiornamento sarà una serie di comandi di modifica e, poiché può essere applicato molto rapidamente, possiamo bloccare il database per applicarlo.

Ma, sarà ancora interessante vedere se ci sono implementazioni di strutture di dati immutabili in javascript, quindi lascerò aperta questa domanda.

Answer 1

L'unico modo per rendere un oggetto immutabile è quello di nasconderlo all'interno di una funzione. È quindi possibile utilizzare la funzione per restituire l'hash predefinito o una versione aggiornata, ma non è possibile archiviare un hash immutabile nell'ambito globale.

function my_hash(delta) { 
    var default = {mykey: myvalue}; 
    if (delta) { 
     for (var key, value in delta) { 
      if (default.hasOwnProperty(key)) default[key] = value; 
     } 
    } 
    return default; 
} 

Non penso che questa sia una buona idea.

Answer 2

Il modo migliore per clonare un oggetto in JavaScript io sappia, è quella contenuta nel underscore.js

Poco:

_.clone = function(obj) { 
    if (!_.isObject(obj)) return obj; 
    return _.isArray(obj) ? obj.slice() : _.extend({}, obj); 
}; 

_.extend = function(obj) { 
    each(slice.call(arguments, 1), function(source) { 
    for (var prop in source) { 
     obj[prop] = source[prop]; 
    } 
    }); 
    return obj; 
}; 

Answer 3

ho avuto gli stessi requisiti per le strutture di dati persistenti per JS, così qualche tempo fa ho realizzato un'implementazione di una mappa persistente. https://github.com/josef-jelinek/cofy/blob/master/lang/feat.js

Contiene l'implementazione di una mappa (ordinata) bilanciata e una mappa naive copy-on-write (e vettore/array persistente non finito).

var map = FEAT.map(); 
var map1 = map.assoc('key', 'value'); 
var value = map1.get('key'); 
var map2 = map1.dissoc('key'); 
... 

supportati altri metodi come count(), contains(key), keys(into = []), values(into = []), toObject(into = {}), toString()

L'implementazione non è troppo complicato ed è di dominio pubblico. Accetto anche suggerimenti e collaboratori :).

Aggiornamento: si possono trovare unit test (esempi di utilizzo) a https://github.com/josef-jelinek/cofy/blob/master/tests/test-feat.html

Update 2: implementazione vettore persistente è ora anche lì con le seguenti operazioni: count(), get(i), set(i, value), push(value), pop(), toArray(into = []), toString()

Answer 4

So che questa domanda è vecchia ma ho pensato che le persone che cercavano come me dovessero puntare a Facebook Immutable.js che offre molti tipi diversi di strutture di dati immutabili in un modo molto efficiente.