R çiftleri neden sıralanmış veriler üzerinde daha iyi performans gösteriyor?

Question

İki işlevin verimliliğini Check if list contains another list in R numaralı yanıtla karşılaştırırken ilginç bir sonuçla karşılaştım. Sıralama, vektör büyük olduğunda duplicated'un verimliliğini büyük ölçüde artırır. Bu, kendi çalışmamda duplicated'u kullanarak önemli bir fark görmediğim için bir sürpriz oldu. Gerçekten de, her gün çalıştığım boyutlar için bir fark yok. Gözlemleyin: Vektör sıralanır zaman

set.seed(1007) 
s1 <- sample(10^2, 10^3, replace = TRUE) 
s1_sort <- sort(s1) 
library(microbenchmark) 
microbenchmark(dp=duplicated(s1), dp_sort=duplicated(s1_sort), times=1000) 
Unit: microseconds 
    expr min  lq  mean median  uq  max neval cld 
    dp 16.459 16.9425 22.06371 17.2965 22.5050 1541.137 1000 a 
dp_sort 17.007 17.5005 25.54953 17.8200 23.3655 1549.198 1000 a 

Gördüğünüz gibi, zamanlamaları hiçbir fark edilebilir bir fark yoktur. Bununla birlikte, çok büyük vektörlerde, sonuçlar çok farklıdır. Aşağıdakileri gözlemleyin:

s2 <- sample(10^6, 10^7, replace = TRUE) 
s2_sort <- sort(s2) 
microbenchmark(dp=duplicated(s2), dp_sort=duplicated(s2_sort), times=100) 
Unit: milliseconds 
    expr  min  lq  mean median  uq  max neval cld 
    dp 816.6883 847.9231 869.6829 861.8210 882.3978 1019.6339 100 b 
dp_sort 287.6779 305.4779 322.8830 315.1198 324.9249 449.1734 100 a 

Neredeyse 3 kat daha hızlı !!! Bu beni burada başlayan tavşan deliğine götürdü: r-source.../duplicated.R. Buradan, çoğaltmanın .Internal(duplicated(x,...)) numaralı telefonu aradığını görüyoruz. Daha sonra pryr::show_c_source(.Internal(duplicated(x))) ve workaround @ 0 (show_c_source'un şu anda sorunlu olduğunu bildiren workaround) işlevini kullanarak duplicated'un do_duplicated numaralı telefonu aradığını görüyoruz. Son olarak, duplicated'un heart'u ortaya çıkar (667 satırından başlar ve 988'de sona erer). Tüm vektör üzerine geçirilir ve sonra bazı karma meydana geldiği göstermektedir: ben tam tüm kodu anlamıyorum

724  /* count unique entries */ 
725  k = 0; 
726  for (i = 0; i < n; i++) 
727   if (LOGICAL(dup)[i] == 0) 
728    k++; 

776  /* Build a hash table, ignoring information on duplication */ 
777  static void DoHashing(SEXP table, HashData *d) 

ama önemli olmamalı sıralama gibi görünüyor. Her iki durumda da vektöre göre (sıralanmış ve karşılaştırılmamış) dönüyoruz ve sonuçta bir vektörün sıralanıp sıralanmadığına bağlı olmayan hash fonksiyonlarının bir çeşidini çağırıyoruz. İlk düşüncem, bir tür dal tahmininin devam ettiğini (bkz. this question), fakat güncellemeden this answer'a, bu şeylerin artık önemli olmaması gerektiği görünüyordu.

Neler oluyor?

DÜZENLEME

boşluk vektörün büyüklüğü ve çiftleri sayısı arttıkça her iki şekilde arttırabilmektedir.

set.seed(496) 
s3 <- sample(10^6, 10^8, replace = TRUE) 
s3_sort <- sort(s3) 
microbenchmark(dp=duplicated(s3), dp_sort=duplicated(s3_sort), times = 10) 
Unit: seconds 
    expr  min  lq  mean median  uq  max neval cld 
    dp 12.149932 12.175665 12.848843 12.495599 12.719861 15.589190 10 b 
dp_sort 2.395636 2.401837 2.706674 2.551375 2.677556 4.373653 10 a 

@alexis_laz hiçbir çoğaltmaları olup olmadığını, sıralama etkisi büyük ölçüde azalır, belirttiği üzere.

s4 <- sample(10^8) 
s4_sort <- sort(s4) 
microbenchmark(dp=duplicated(s4), dp_sort=duplicated(s4_sort), times = 10) 
Unit: seconds 
    expr  min  lq  mean median  uq  max neval cld 
    dp 8.013995 8.130565 8.593626 8.197501 8.438703 10.639452 10 b 
dp_sort 6.135788 6.158140 6.751101 6.256739 7.241381 8.913507 10 a 

Answer 1

Önemli etken, CPU önbellek kayıplarının oranı ve boyut ölçekleri olarak daha pahalı sayfa hatalarıdır. Çoğaltma, basit bir karma tabloya referans ile kontrol edilir. Sorgulanan hash tablosunun bölümü zaten yüksek hızlı bellek önbelleğinde ise, bu aramalar çok daha hızlıdır. Küçük vektörler için, karşılık gelen karma tablo, yüksek hızlı bellek önbelleğine tamamen sığar, bu yüzden erişim sırasının anlamı önemli değildir, ilk karşılaştırmanızda gördüğünüz şey budur.

Daha büyük vektörler için, karma tablonun yalnızca bazı blokları, herhangi bir zamanda önbelleğe sığar. Çoğaltmalar ardışık ise, arama için gereken karma tablonun bölümü, daha sonraki aramalar için önbellekte zaten mevcut olacaktır. Bu nedenle performans, daha büyük vektörler için çoğaltılarak artar. Son derece büyük vektörler için, karma tablosu, mevcut fiziksel belleğe tamamen sığmayabilir ve diske dağıtılabilir, böylece fark daha da belirgin hale gelir.

Bunu test etmek için, orijinal gönderinin s2 vektörünü ve sıralı sürümünü kullanalım, aynı zamanda kopyaların yalnızca birbirinin yanında olduğunu ancak başka şekilde sıralanmamış olduğunu test edin.

# samples as in original post 
s2 <- sample(10^6, 10^7, replace = TRUE) 
s2_sort <- sort(s2) 

# in the same order as s2, but with duplicates brought together 
u2 <- unique(s2) 
t2 <- rle(s2_sort) 
s2_chunked <- rep(u2,times=t2$length[match(u2,t2$values)]) 

Ayrıca, yalnızca karma değerine göre sıralama yapmayı da düşünelim. R'deki karma kodlamayı tahmin edeceğim, ancak imzasız uzun ürünler kullanabilmekten ziyade çift boyutlu değerlerle uğraşıyoruz, böylece bitly ops kullanamayacağız.

# in the order of hash value 
K <- ceiling(log2(length(s2)*2)) 
M <- 2^K 
h <- ((3141592653 * s2) %% 2^32)/2^(32-K) 
ho <- order(h) 
s2_hashordered <- s2[ho] 

Ne görmeyi bekliyoruz performans s2_sort ve s2_chunked ve s2_hashordered için daha da iyi için benzer olmasıdır. Bu vakaların her birinde, önbellek kayıplarını en aza indirmeye çalıştık.

microbenchmark(
duplicated(s2), 
duplicated(s2_sort), 
duplicated(s2_chunked), 
duplicated(s2_hashordered), 
times=10) 

Unit: milliseconds 
         expr  min  lq  mean median  uq  max neval cld 
      duplicated(s2) 664.5652 677.9340 690.0001 692.3104 703.8312 711.1538 10 c 
     duplicated(s2_sort) 245.6511 251.3861 268.7433 276.2330 279.2518 284.6589 10 b 
    duplicated(s2_chunked) 240.0688 243.0151 255.3857 248.1327 276.3141 283.4298 10 b 
duplicated(s2_hashordered) 166.8814 169.9423 185.9345 185.1822 202.7478 209.0383 10 a