JavaScript'te En Yakın Eşlik Algoritması

Question

JavaScript kullanarak rasgele oluşturulmuş bir dizi noktadaki en yakın puan çiftini bulmak için bir böl ve yönet algoritması uygulamaya çalışıyorum. Bu algoritma O (n log n) zamanında çalışmalıdır, ancak O (n^2) olması gereken basit bir kaba kuvvet algoritmasından daha uzun sürmektedir.

İki jsfiddles o zaman oluşturduk 16000 noktaları dizisi için algoritmalar:

• Divide and Conquer
• Brute Force

Varsayımım bölmek ve fethetmek çünkü çok yavaş olmasıdır JavaScript dizileri aslında karma tablolarıdır. JavaScript'teki algoritmayı önemli ölçüde hızlandırmak mümkün mü? Eğer öyleyse, bunu yapmanın en iyi yolu ne olurdu?

Answer 1

Bir bakışta, birleştirme işleviniz çok fazla bellek ayırıyor (yaklaşık olarak O (n^2)). Bu here ölçmek için hacky bir yol yaptım. Temel fikir, sadece küresel kapsamda bir sayacım var ve her çağrıldığında birleştirme tarafından oluşturulan dizinin boyutunu ekliyorum. Umarım bu sizin düzeltmeniz için yeterli bilgi, daha fazla sorunla karşılaşırsanız birkaç ek işaretçi sunmaktan mutluluk duyarım.

Ayrıca, sadece rakamlarla oynayarak bir hash tablosu sorunu olduğunu göz ardı etmek oldukça kolaydır * - karma tablosu tarafından yavaşlatılan bir algoritma O (n log n) 'den daha hızlı bir büyüme oranı göstermez, sadece yavaş başlar ve aynı hatlar boyunca büyürler. Bir dizi değeri denerseniz, bundan daha hızlı büyüdüğü ve farklı bir sorun olduğu ortaya çıkacaktır.

* javascript Dizilerin iç uygulama biraz daha karmaşık onlardan daha adil olmak nesneler, ama noktası için bu gerçekten olursa olsun [bu post] (http inanıyoruz