пазбегнуць дубляваныя ключы, каб атрымаць выпадковую хэш-ключ

Мне трэба, каб выбраць запіс хэш выпадковым чынам, так што я

h = {1 => 'one', 2 => 'two', 3 => 'three'}
k = h.keys.sample
result = h[k]

Так як h.keys стварае новы масіў не падабаецца. Ці ёсць спосаб, каб пазбегнуць стварэння новага масіва кожны раз?

3
Я згодны з заўвагамі пра тое, што я не павінен марнаваць на гэта час, так што я ў канчатковым выніку з тым жа кодам, як я адправіў. Я проста спытаў з цікаўнасці. Я думаю, што гэта можна зрабіць элегантна, пералічваючы ключы і выбар кожнага ключа з памяншэннем верагоднасці.
дададзена аўтар akonsu, крыніца
@Linuxios: так, гэта галоўны клопат паста. што ты маеш на ўвазе?
дададзена аўтар akonsu, крыніца
@Linuxios: так, гэта галоўны клопат паста. што ты маеш на ўвазе?
дададзена аўтар akonsu, крыніца
@akonsu: Выклік h.keys ўсё яшчэ стварае новы масіў.
дададзена аўтар Linuxios, крыніца
Чаму б вам не падабаецца, што ён стварае новы масіў? Калі гэты код ці не знаходзіцца ў кропцы доступу накладныя выдаткі тут не павінна быць вельмі значным.
дададзена аўтар Puhlze, крыніца
Таксама гл stackoverflow.com/questions/15454632/&hellip, для падобнага абмеркавання
дададзена аўтар Puhlze, крыніца

11 адказы

Я хацеў бы паўтарыць тое, што першыя кажуць большасць людзей: гэта, верагодна, не мае значэння.

Па-другое, я пакажу, што ён упэўнены, здаецца, што вы хочаце выпадковы значэнне , а не выпадковы ключ . Можа быць, гэта толькі таму, што ваш прыклад фрагмента кода не паказвае, што вы сапраўды робіце.

Калі вы вельмі часта трэба выпадковае значэнне, і вельмі рэдка абнаўляць Hash, я рэкамендаваў бы кэшаваць любыя значэнні часу хэша мадыфікуецца, а затым прымае выпадковае значэнне з кэша. Адзін са спосабаў зрабіць гэта можа выглядаць так:

class RandomValueHash < Hash
  def []=(k, v)
    super(k, v)
    @values = self.values
  end

  def sample_value
    @values ||= self.values
    @values.sample
  end
end

rvh = RandomValueHash[{1 => 'one', 2 => 'two', 3 => 'three'}]
rvh.sample_value
# => "one"
rvh[4] = 'four'
rvh[5] = 'five'
rvh.sample_value
# => "four"

Вядома, калі вы сапраўды хочаце выпадковы ключ, а не ад значэння, дакладна такая ж канцэпцыя ўжываецца. У любым выпадку, гэта дазваляе пазбегнуць узнаўляючы масіў кожны раз, калі вы атрымліваеце значэнне; яна толькі стварае яго ў выпадку неабходнасці.

2
дададзена
дзякуй, я быў занепакоены не пра хуткасці, а аб спажыванні памяці. вось артыкул, якую я знаходжу цікавым: github.com/блог/1489-эй-Judy-дон-т-зрабіць-гэта дрэнна
дададзена аўтар akonsu, крыніца
@pjs Дзякуй! Я бы старанна заблытацца, калі б гэта было не істотна хутчэй, чым прынята рашэнне, якое павінна прайсці праз Hash, каб дасягнуць жаданага ключ/значэнне кожны раз. У вас тэстах, вы параўнаць агульнапрынятае рашэнне арыгінальны пытанне? Мне было б цікава, колькі гэта сапраўды дапамагае на практыцы.
дададзена аўтар Darshan Rivka Whittle, крыніца
Гэта адлюстроўвае тое, што я прапаноўваў, але ў аўтаматычным рэжыме, а не ручной моды. Прэстыжнасць! На маю бенчмаркетынгу гэта значна хутчэй, чым прынята рашэнне, і адносная прадукцыйнасць становіцца яшчэ лепш, так як лік значэнняў у хэш павялічваецца.
дададзена аўтар pjs, крыніца
Я дадам код тэстаў на мой адказ, каб людзі маглі прыйсці да сваіх уласных высноў.
дададзена аўтар pjs, крыніца
@akonsu Калі вашу ўвагу спажыванне памяці, то вы павінны любіць рашэнні, якія генеруюць ключ ўсталяваць адзін раз і шматразова выкарыстоўваць яго. Рашэнне даршан з'яўляецца даволі элегантна: ён эфектыўны на памяці, хутка на тэстах, і не патрабуе ручнога ўтрымання.
дададзена аўтар pjs, крыніца

Гэта не будзе ствараць яшчэ адзін масіў. У сярэднім <�моцны> hash_random_value будзе перабіраць на паўдарогі праз дадзены хэш, каб атрымаць выпадковае значэнне.

def hash_random_value(h)
  i = rand(h.length)
  h.each_with_index do |(_, v), i2|
    return v if i == i2
  end
end

h = {1 => 'one', 2 => 'two', 3 => 'three'}
hash_random_value(h)

Гэта, як гаворыцца, вы павінны аптымізаваць толькі тады, калі вы ўпэўнены, што вам трэба зрабіць гэта. Адзіны спосаб, якім Вы можаце даведацца гэта свой код, у адваротным выпадку вы, хутчэй за ўсё, рабіць заўчасную аптымізацыю. гэта значыць ускладняючы свой код і павялічваючы верагоднасць ўнясення памылак - часам нават зніжаецца прадукцыйнасць праграмы. Ваша арыгінальнае рашэнне значна лягчэй зразумець, чым у мяне, і гэта адразу відаць, што гэта правільна.

2
дададзена
Так. крута. гэта вельмі блізка да майго рашэння, што я дадаў у адказ таксама, але больш эфектыўна. дзякуй.
дададзена аўтар akonsu, крыніца
гэта перапісчык так дорага, як дублікат масіва?
дададзена аўтар akonsu, крыніца
Вы ствараеце аб'ект Enumerator :)
дададзена аўтар three, крыніца
На практыцы ні адзін не вельмі дорага. У тэорыі перечислитель патрабуе пастаяннага аб'ёму памяці, у той час як спажыванне памяці на масіве расце з памерам масіва. З іншага боку, менш рэсурсаёмісты перабраць масіў, чым лічыльніку. Вы часта можаце гандляваць спажыванне памяці для цыклаў цэнтральнага працэсара і наадварот. У любым выпадку, калі гэта сапраўды мае значэнне, вы павінны свой код: github.com/ruby-prof/ лалава-праф
дададзена аўтар Robert Kajic, крыніца

Гэта не будзе ствараць яшчэ адзін масіў. У сярэднім <�моцны> hash_random_value будзе перабіраць на паўдарогі праз дадзены хэш, каб атрымаць выпадковае значэнне.

def hash_random_value(h)
  i = rand(h.length)
  h.each_with_index do |(_, v), i2|
    return v if i == i2
  end
end

h = {1 => 'one', 2 => 'two', 3 => 'three'}
hash_random_value(h)

Гэта, як гаворыцца, вы павінны аптымізаваць толькі тады, калі вы ўпэўнены, што вам трэба зрабіць гэта. Адзіны спосаб, якім Вы можаце даведацца гэта свой код, у адваротным выпадку вы, хутчэй за ўсё, рабіць заўчасную аптымізацыю. гэта значыць ускладняючы свой код і павялічваючы верагоднасць ўнясення памылак - часам нават зніжаецца прадукцыйнасць праграмы. Ваша арыгінальнае рашэнне значна лягчэй зразумець, чым у мяне, і гэта адразу відаць, што гэта правільна.

2
дададзена
Так. крута. гэта вельмі блізка да майго рашэння, што я дадаў у адказ таксама, але больш эфектыўна. дзякуй.
дададзена аўтар akonsu, крыніца
гэта перапісчык так дорага, як дублікат масіва?
дададзена аўтар akonsu, крыніца
Вы ствараеце аб'ект Enumerator :)
дададзена аўтар three, крыніца
На практыцы ні адзін не вельмі дорага. У тэорыі перечислитель патрабуе пастаяннага аб'ёму памяці, у той час як спажыванне памяці на масіве расце з памерам масіва. З іншага боку, менш рэсурсаёмісты перабраць масіў, чым лічыльніку. Вы часта можаце гандляваць спажыванне памяці для цыклаў цэнтральнага працэсара і наадварот. У любым выпадку, калі гэта сапраўды мае значэнне, вы павінны свой код: github.com/ruby-prof/ лалава-праф
дададзена аўтар Robert Kajic, крыніца

Калі вам трэба зрабіць выпадковую выбарку шмат, і трэба, каб быць эфектыўным, то, магчыма, лал Hash не правільны структура дадзеных або для захоўвання вашай праблемы. Нават клас-абалонка, якая падтрымліваецца Hash і Масіў атрыбуты разам маглі б працаваць добра - калі, напрыклад, для кожнай запісы ў хэш, што вам неабходна, каб прачытаць 20 выпадковых выбарак.

Будзь ці не тое, што працуе для вас, залежыць не толькі ад суадносін чытання і запісы, гэта таксама адносіцца да лагічнай структуры вашых дадзеных задачы (у адрозненне ад таго, як вы абралі, каб прадставіць яго ў растворы).

Але перш чым адправіцца на пераасэнсаванне вашу праблему, вы павінны мець практычную патрэба ў больш высокай прадукцыйнасці ў здзіўленым кодзе. Хэш павінны быць досыць вялікімі, каб мець прыкметнае затраты на выманне яго ключы. <�Код> h.keys займае каля 250 мс, калі хэш мае 1 мільёна запісаў на маім ноўтбуку.

1
дададзена

Як наконт ...

h = {1 => 'one', 2 => 'two', 3 => 'three'}
k = h.keys
...
result = h[k.sample]

Вы можаце зрабіць Result = ч [k.sample] раз так часта, як вам падабаецца, і гэта не будзе рэгенераваць да масіў. Тым не менш, вы павінны рэгенераваць да любы час ч змены.

ADDENDUM: I'm throwing in benchmark code for several of the proposed solutions. Enjoy.

#!/usr/bin/env ruby
require 'benchmark'

NUM_ITERATIONS = 1_000_000

def hash_random_value(h)
  i = rand(h.length)
  h.each_with_index do |(_, v), i2|
    return v if i == i2
  end
end

class RandomValueHash < Hash
  def []=(k, v)
    super(k, v)
    @values = self.values
  end

  def sample_value
    @values ||= self.values
    @values.sample
  end
end

Benchmark.bmbm do |b|
  h = {1 => 'one', 2 => 'two', 3 => 'three'}

  b.report("original proposal") do
    NUM_ITERATIONS.times {k = h.keys.sample; result = h[k]}
  end

  b.report("hash_random_value") do
    NUM_ITERATIONS.times {result = hash_random_value(h)}
  end

  b.report("manual keyset") do
    k = h.keys
    NUM_ITERATIONS.times {result = h[k.sample]}
  end

  rvh = RandomValueHash[{1 => 'one', 2 => 'two', 3 => 'three'}]

  b.report("RandomValueHash") do
    NUM_ITERATIONS.times {result = rvh.sample_value}
  end
end
1
дададзена
Гэта тое ж самае, як рашэнне Ора ст.
дададзена аўтар Linuxios, крыніца
@NeilSlater, праўда, я спрабую рашэнне C.
дададзена аўтар Linuxios, крыніца
Добрая праца на тэстах! Для таго, каб знайсці лепшае рашэнне, тэсты павінны вымяраць код выканання ўсіх подзадач ў рэальных колькасцях і з рэалістычнымі аб'ёмамі дадзеных. Вельмі малаверагодна, што ОП хоча стварыць 3-элементная Хэш адзін раз, а затым паспрабаваць гэта ў мільён разоў. Але ніякія лічбы не былі заяўлены, так да OP, каб пашырыць гэта, калі гэта неабходна, каб высветліць, лепшае рашэнне для сваёй праблемы.
дададзена аўтар Neil Slater, крыніца
Гэта робіць прынамсі, спробу ADRESS заклапочанасці Op адносна эфектыўнасці, а таксама можа аказацца самым простым кампрамісам.
дададзена аўтар Neil Slater, крыніца
@NeilSlater Дзякуй. Але я не згодны аб выкананнi ўсiх подзадач ў рэальных колькасцях для параўнання. Вялікія колькасці паўтораў даюць больш стабільныя адзнак адносных выдаткаў , і можна маштабаваць на велічыню паўтарэння, каб паказаць кошт адзінкі подзадачи. Тое, што я ўбачыў у цесцю, што на практыцы гэта не з'яўляецца праблемай, паколькі многія з іх паказалі. Але я таксама бачыў, што прынятае рашэнне з'яўляецца найбольш павольна, прыкладна ў 3 разы больш павольна, чым арыгінальны падыход, матываванага на пытанне OP, і калі ёсць больш элементаў у хэш яго адносная прадукцыйнасць нават горш.
дададзена аўтар pjs, крыніца
@Linuxios Ня насамрэч - маё намер складалася ў тым, што код вышэй ... выконваецца адзін раз, і генеруе адзін масіў ключоў, якія могуць быць даступныя ў сотні разоў ніжэй ... без неабходнасці рэгенераваць масіў, калі толькі ч змены.
дададзена аўтар pjs, крыніца

Як наконт ...

h = {1 => 'one', 2 => 'two', 3 => 'three'}
k = h.keys
...
result = h[k.sample]

Вы можаце зрабіць Result = ч [k.sample] раз так часта, як вам падабаецца, і гэта не будзе рэгенераваць да масіў. Тым не менш, вы павінны рэгенераваць да любы час ч змены.

ADDENDUM: I'm throwing in benchmark code for several of the proposed solutions. Enjoy.

#!/usr/bin/env ruby
require 'benchmark'

NUM_ITERATIONS = 1_000_000

def hash_random_value(h)
  i = rand(h.length)
  h.each_with_index do |(_, v), i2|
    return v if i == i2
  end
end

class RandomValueHash < Hash
  def []=(k, v)
    super(k, v)
    @values = self.values
  end

  def sample_value
    @values ||= self.values
    @values.sample
  end
end

Benchmark.bmbm do |b|
  h = {1 => 'one', 2 => 'two', 3 => 'three'}

  b.report("original proposal") do
    NUM_ITERATIONS.times {k = h.keys.sample; result = h[k]}
  end

  b.report("hash_random_value") do
    NUM_ITERATIONS.times {result = hash_random_value(h)}
  end

  b.report("manual keyset") do
    k = h.keys
    NUM_ITERATIONS.times {result = h[k.sample]}
  end

  rvh = RandomValueHash[{1 => 'one', 2 => 'two', 3 => 'three'}]

  b.report("RandomValueHash") do
    NUM_ITERATIONS.times {result = rvh.sample_value}
  end
end
1
дададзена
Гэта тое ж самае, як рашэнне Ора ст.
дададзена аўтар Linuxios, крыніца
@NeilSlater, праўда, я спрабую рашэнне C.
дададзена аўтар Linuxios, крыніца
Добрая праца на тэстах! Для таго, каб знайсці лепшае рашэнне, тэсты павінны вымяраць код выканання ўсіх подзадач ў рэальных колькасцях і з рэалістычнымі аб'ёмамі дадзеных. Вельмі малаверагодна, што ОП хоча стварыць 3-элементная Хэш адзін раз, а затым паспрабаваць гэта ў мільён разоў. Але ніякія лічбы не былі заяўлены, так да OP, каб пашырыць гэта, калі гэта неабходна, каб высветліць, лепшае рашэнне для сваёй праблемы.
дададзена аўтар Neil Slater, крыніца
Гэта робіць прынамсі, спробу ADRESS заклапочанасці Op адносна эфектыўнасці, а таксама можа аказацца самым простым кампрамісам.
дададзена аўтар Neil Slater, крыніца
@NeilSlater Дзякуй. Але я не згодны аб выкананнi ўсiх подзадач ў рэальных колькасцях для параўнання. Вялікія колькасці паўтораў даюць больш стабільныя адзнак адносных выдаткаў , і можна маштабаваць на велічыню паўтарэння, каб паказаць кошт адзінкі подзадачи. Тое, што я ўбачыў у цесцю, што на практыцы гэта не з'яўляецца праблемай, паколькі многія з іх паказалі. Але я таксама бачыў, што прынятае рашэнне з'яўляецца найбольш павольна, прыкладна ў 3 разы больш павольна, чым арыгінальны падыход, матываванага на пытанне OP, і калі ёсць больш элементаў у хэш яго адносная прадукцыйнасць нават горш.
дададзена аўтар pjs, крыніца
@Linuxios Ня насамрэч - маё намер складалася ў тым, што код вышэй ... выконваецца адзін раз, і генеруе адзін масіў ключоў, якія могуць быць даступныя ў сотні разоў ніжэй ... без неабходнасці рэгенераваць масіў, калі толькі ч змены.
дададзена аўтар pjs, крыніца

нешта накшталт гэтага:

h.each_with_index.reduce(nil) {|m, ((_, v), i)|
  rand(i + 1) == 0 ? v : m
}
0
дададзена

нешта накшталт гэтага:

h.each_with_index.reduce(nil) {|m, ((_, v), i)|
  rand(i + 1) == 0 ? v : m
}
0
дададзена

Калі ў вас ёсць гіганцкі хэш, гэта бессэнсоўна непакой. Рубін ня эфектыўнасць электрастанцыі, і калі вы што непакоіцца пра гэта, вы павінны выкарыстоўваць C (++).

0
дададзена

Не зусім. Хэш не мае індэкса, каб вы альбо пераўтварыць іх у масіў і выбраць выпадковы індэкс ці перанумараваць хэш для выпадковага ліку раз. Вы павінны эталонны метад з'яўляецца самым хуткім, але я сумняваюся, што вы можаце пазбегнуць стварэння новага аб'екта.

Калі вы не клапоціцеся аб вашым аб'екце можна перакласці гэты ключы для выпадковага ліку раз, але тады вы церат масіваў для вяртаюцца значэнняў.

0
дададзена

Не зусім. Хэш не мае індэкса, каб вы альбо пераўтварыць іх у масіў і выбраць выпадковы індэкс ці перанумараваць хэш для выпадковага ліку раз. Вы павінны эталонны метад з'яўляецца самым хуткім, але я сумняваюся, што вы можаце пазбегнуць стварэння новага аб'екта.

Калі вы не клапоціцеся аб вашым аб'екце можна перакласці гэты ключы для выпадковага ліку раз, але тады вы церат масіваў для вяртаюцца значэнняў.

0
дададзена