リストと辞書へのランダムアクセス

listvsdict.vim

let s:R = vital#of("vital").import("Random")

" @param n: length of list/dict
" @param m: # of loop
function! g:Go(n, m)

  let list = range(a:n)
  let a = s:R.shuffle(list)
  let dict = {}
  for i in list
    let dict[i] = i
  endfor

  let tl = 0
  let td = 0

  for i in range(a:m)
    let T0 = reltime()
    let num = 0
    for i in a
      let num += list[i]
    endfor
	let T1 = reltime()
	let tl += 1000000*(T1[0]-T0[0])+T1[1]-T0[1]

    let T0 = reltime()
    let num2 = 0
    for i in a
      let num2 += dict[i]
    endfor
	let T1 = reltime()
	let td += 1000000*(T1[0]-T0[0])+T1[1]-T0[1]

    if num != num2
      echo "???"
    endif
  endfor

  return printf("len=%6d, loop=%5d, list=%8d, dict=%8d",a:n,a:m,tl,td)
endfunction


echo g:Go(   30, 50)
echo g:Go(   50, 50)
echo g:Go(   80, 50)
echo g:Go(   90, 50)
echo g:Go(  100, 50)
echo g:Go(  110, 50)
echo g:Go(  120, 50)
echo g:Go(  150, 50)
echo g:Go(  200, 50)
echo g:Go(  500, 50)
echo g:Go(  800, 50)
echo g:Go( 1000, 50)
echo g:Go( 3000, 50)
echo g:Go( 5000, 50)
echo g:Go( 7000, 50)
echo g:Go(10000, 50)

n= 100, m=10000, tl=4110134, td=4417413
n= 10000, m= 10, tl=951709, td=459767

n= 100, m=10000, tl= 0.000196, td= 0.000207
n= 10000, m= 10, tl= 0.114469, td= 0.067165

len=    30, loop=   50, list=    3379, dict=    3520
len=    50, loop=   50, list=    5505, dict=    5681
len=    80, loop=   50, list=    8471, dict=    8772
len=    90, loop=   50, list=    9769, dict=   10518
len=   100, loop=   50, list=   10755, dict=   11190
len=   110, loop=   50, list=   12203, dict=   12090
len=   120, loop=   50, list=   13545, dict=   13259
len=   150, loop=   50, list=   15942, dict=   16685
len=   200, loop=   50, list=   24981, dict=   22357
len=   500, loop=   50, list=   59925, dict=   59114
len=   800, loop=   50, list=  101584, dict=   92238
len=  1000, loop=   50, list=  131091, dict=  109595
len=  3000, loop=   50, list=  516990, dict=  341688
len=  5000, loop=   50, list= 1198906, dict=  652359
len=  7000, loop=   50, list= 1807676, dict=  858635
len= 10000, loop=   50, list= 3284810, dict= 1309388