Mümkün olan en hızlı işlevsel güncelleştirmeyle dizi benzeri bir veri yapısına ihtiyacım var. Bana bu özelliği (Braun, Rastgele Erişim Listeleri) sağlayan esnek dizilerden oluşan birkaç farklı uygulama gördüm, ancak ilgilenmeyeceğimiz veya eklenmeyeceğimiz durumlar için özel olarak optimize edilmiş bir uygulama olup olmadığını merak ediyorum - sadece güncellemeler.İşlevsel güncellemelere sahip dizilerin en verimli uygulaması nedir?
Jean-Christophe Filliâtre ki (burada kalıcı dizileri temel bir bileşenidir, birleşim bulma yaklaşık kalıcı olan) aynı sayfada bağlı the paper anlatılan, sürekli dizilerin a very nice implementation sahiptir. Kod doğrudan there kullanılabilir.
fikri dizinin "son sürümü" O(1) erişim ve güncelleme işlemleri ile, bir zamanki dizisi olarak temsil edilir ve önceki sürümlerinde bu son sürüm olarak temsil edilir, ayrıca farklılıkların bir liste olması. Yapının bir önceki sürümüne erişmeye çalışırsanız, dizi farklılıkları uygulamak ve etkin gösterimi tekrar sunmak için "yeniden yönlendirilir".
Bu, elbette tüm iş akışlarında O (1) olmayacaktır (yapının ilgisiz sürümlerine sürekli olarak erişir ve bunları değiştirirseniz, sık sık yeniden maliyetlendirme yaparsınız), ancak çoğunlukla bir sürümle çalışan genel iş akışı için, ve bazen "son sürüm" haline gelen ve güncellemeleri alan eski bir sürüme geri dönüyor, bu çok verimli. Gözlemsel olarak saf bir arayüz altında gizlenmiş çok hoş bir mutabilite kullanımı.
Hangi dili kullanıyorsunuz? Haskell'de, mutable arrays'u eyalet monadıyla kullanabilirsiniz ve Mercury'de IO durumunu işleyerek değişken dizileri kullanabilirsiniz. Ocaml ayrıca, ne yazık ki, referanssal şeffaflık sağlamayan bir dizi modülüne de sahiptir.
OCaml kullanıyorum. Soruyu, Haskell'in toplumun bu şeylere ilişkin bilgisine dokunacak şekilde etiketledim. Btw, STArray'ın eski kopyayı etkin bir şekilde saklarken bir diziyi güncellemeyi kullanma problemimi nasıl çözeceğinden emin değilim. – rgrinberg
OCaml dizileri değişebilir, kalıcılığı yoktur. Güncelleme ve kalıcılık ile sürekli zaman erişim imkansız değilse oldukça zor görünüyor. Yani, bir harita muhtemelen istediğiniz (muhtemelen yukarıda belirtildiği gibi). –
Birçok farklı harita tabanlı uygulama var, kullanım durumum için en iyisini arıyorum. Örneğin, bu uygulama için dengeli bir BST korkunç olurdu. Asimptotik performans aynı olsa da. – rgrinberg
Ben de fonksiyonel diziler gerekli ve birkaç gün önce bu SO soru üzerine hissetti. Gasche'ın yeni bir dizi oluşturması için önerdiği çözümden memnun olmadım, pahalı bir işlem ve dizinin eski sürümlerine oldukça sık erişmem gerekiyor (bunu bir dizi üzerinde oynayan AI alfa/beta uygulaması için kullanmayı planlıyorum).
(Pahalı olduğunu söylediğimde, sanırım o, tarihin büyüklüğü olan O (n * h) 'dir, çünkü en kötü durumda tek bir hücre tekrar tekrar güncellendi ve her bir güncelleme listesi için tüm güncelleme listesinden geçilmesi gerekiyordu. Ayrıca, dizinin yeniden yönlendirilmesi gerektiğinde hücrelerin çoğunun güncellenmemesini beklerim).
Bu başka bir yaklaşım öneriyoruz neden, belki burada biraz geribildirim alabiliriz. Benim fikrim, bir B-Ağacında olduğu gibi diziyi saklamaktır, çünkü değişebilir olmadığından, herhangi bir değeri kolayca indeksleyebilirim. https://github.com/shepard8/ocaml-ptarray:
Ben projenin depo üzerinde küçük bir giriş yazdı. Sipariş, ağacın derinliğine ve sırasına göre seçilmiştir, bu yüzden sadece get/set işlemleri sırasına göre güzel karmaşıklıklar elde edebilirim, yani O (k^2). k ile= 10 ı kadar 10^10 değer saklayabilir. Aslında dizilerim 200'den fazla değer içermemelidir, ancak bu, çözümümün ne kadar güçlü olması gerektiğini göstermektir.
Herhangi bir öneri hoş geldiniz!
Kesinlikle bir çeşit harita? –
@ DominicBou-Samra değişmez bir harita? diziden daha pahalı olmaz mıydı? –
Dominic, haritalar, Braun ve RAL tüm ağaç tabanlı. Saf ağaç tabanlı veri yapısını yenebilen bir zorunlu dizi (mutasyona uğramamış) ile akıllıca bir kombinasyonun olup olmadığını görmek istiyorum. – rgrinberg