Düşük karmaşıklık tamsayı vektörlerinin verimli gösterimi

Question

V tamsayıların bir vektörü olsun ve L'un V uzunluğunu olmasına izin verin.

Şimdi, V içinde farklı değerlerin sayısı Kdaha küçük daha L olduğunu varsayalım.

bir de N ardışık sürekli "blok" bir birleştirme şeklinde, böylece V, kriteri olduğu kabul edilebilir.

Son olarak, bir V bundan böyle salt okunur ( aka değişmez) 'dir, yani bir kez başlatıldı varsayabiliriz.

saklamak için savurganlıktır (şu anda çalışıyorum durumda, L olarak N 10 ile 10 ve yaklaşık 20 olduğu) standart MATLAB L uzun vektörü gibi düşük karmaşıklıktaki veriler. MATLAB herhangi yerleşik

1. düzenli vektörü olarak aynı arayüze sahip veri yapısı (örneğin bir ifade V(k) ile olan son öğe ile k-inci elemanı okuyabilir var mı V(end), V(p:q) ile konumların aralıkları, vb.).
2. , bir tam sayı büyüklüğünden L ×  'dan daha az depolama alanı kullanır.

?

---

btw, sorun oldukça aynı (en azından AFAICT) seyrek dizi gösterimi edilene andırır, ancak.

---

Tamam, burada gariepy en yanıta göre benim çözüm, var:

block_sizes = [5, 4, 3, 2]; 
block_values = 1000 + (1:numel(block_sizes)); 
interpolation_table = [0 cumsum(block_sizes)]; 
V = @(i) interp1(interpolation_table, [NaN block_values], i, 'next'); 
V(0) 
ans = 
    NaN 

V(1:5) 
ans = 
     1001  1001  1001  1001  1001 

V(6:9) 
ans = 
     1002  1002  1002  1002 

V(10:12) 
ans = 
     1003  1003  1003 

V(13:14) 
ans = 
     1004  1004 

V(15) 
ans = 
    NaN 

olsa minik siğil vardır: bir yükseltilmiş eğer

V(end) 
ans = 
     1001 

(Daha iyi olurdu tamamen deli cevap vermek yerine argümanlar olarak end, verilen istisna.)

---

^{Tabii ki, her zaman böyle bir şeyin kendi uygulamamı gerçekleştirmeye çalışabileceğimi biliyorum, ancak bundan kaçınabilirse tekerlekleri yeniden icat etmemeyi tercih ederim.}

Answer 1

Bu verileri temsil etmek için olası bir yöntem, bir enterpolasyon tablosudur.

vec uzunluğunuz L vektörü olduğunu varsayalım. Sonra

[num_occurrences, y_values] = hist(vec, unique(vec)); 

interpolasyon temsilini oluşturmak: Birincisi, yineleme sayısını hesaplamak Nihayet

interp_table = zeros(1,length(y_values) + 1); 
interp_table(1) = 1; 
y_values(end+1) = y_values(end) + 1; % Need to create a "fake" value at the end of the interpolation table 
for i = 2:length(y_values) 
    interp_table(i) = interp_table(i-1) + num_occurrences(i-1); 
end 

, size istediğiniz "dizi benzeri" erişim sağlamak için bir işlev kolunu tanımlar.

my_fun = @(x) interp1(interp_table, y_values, x, 'previous'); 

Örnek:

>> vec = [1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 ]; 
>> my_fun(1) 
ans = 
    1 
>> my_fun(2) 
ans = 
    1 
>> my_fun(3) 
ans = 
    2 
>> my_fun(6) 
ans = 
    2 
>> my_fun(7) 
ans = 
    2 
>> my_fun(8) 
ans = 
    3 
>> my_fun(17) 
ans = 
    3 
>> my_fun(18) %% This is vec(L+1), so it should never be needed 
ans = 
    4 
>> my_fun(19) %% Above index L+1, values are not defined 
ans = 
    NaN 

örnekler

küçük bir ihtar gösterilmektedir: my_fun (L) üzerinde değerler L interpolasyon ile temsil edilen orijinal vektör uzunluğudur, kullanılmamalıdır tablo. Yani bu size dizi benzeri erişim sağlar, ancak bu enterpolasyon tablosunun "uzunluğunu" doğrudan hesaplayamazsınız.

>> my_fun(1:17) 
ans = 
    Columns 1 through 15 
    1  1  2  2  2  2  2  3  3  3  3  3  3  3  3 
    Columns 16 through 17 
    3  3