基于直方图/频率哈希表的随机抽样算法技术问询

Great question! Let's break this down into the two core problems you're tackling—weighted sampling with and without replacement from a frequency hash table—and walk through statistically valid approaches plus Common Lisp implementations.

1. Sampling with Replacement (Preserving Original Distribution) #

To sample while retaining the original probability distribution (allowing duplicates), the standard approach is weighted random sampling using a cumulative distribution function (CDF). It’s straightforward to implement and works well for most practical use cases. Here’s how it works:

• Calculate the total sum of all frequencies in your hash table. This represents the "range" of your weighted distribution.
• Generate a random number between 0 (inclusive) and the total frequency sum (exclusive).
• Iterate through the hash table, accumulating frequencies until the accumulated sum exceeds the random number. The corresponding key is your sampled item.

For high-performance repeated sampling, you could also use the Alias Method (precomputes a lookup table for O(1) sampling), but the CDF method is simpler for one-off or low-volume sampling tasks.

2. Sampling without Replacement: Is Your Approach Statistically Valid? #

Short answer: Yes, your approach is fully compliant with statistical standards!

When you remove a sampled item from the hash table, you’re preserving the relative probabilities of the remaining items exactly as they should be for an unbiased无放回抽样. This is the standard way to perform weighted without-replacement sampling—each draw adjusts the available pool to maintain the correct relative weights for subsequent picks.

Common Lisp Implementation #

Below are functions that handle both sampling modes, with options to modify the original hash table or work with a copy for non-destructive无放回抽样.

Helper & Core Functions #

(defun total-frequency (hash-table)
  "Calculate the sum of all frequency values in the hash table."
  (let ((total 0))
    (maphash (lambda (k v) (declare (ignore k)) (incf total v)) hash-table)
    total))

(defun sample-with-replacement (hash-table)
  "Sample a single item from the hash table (with replacement, preserves original distribution)."
  (let* ((total (total-frequency hash-table))
         (r (random total)))
    (loop with accumulator = 0
          for key being the hash-keys of hash-table
          for freq = (gethash key hash-table)
          do (incf accumulator freq)
          when (> accumulator r)
            return key)))

(defun sample-without-replacement (hash-table &key (modify-original t))
  "Sample a single item without replacement. If MODIFY-ORIGINAL is T, alters the input hash table; otherwise returns sampled key + updated copy."
  (let* ((target-table (if modify-original
                           hash-table
                           (let ((copy (make-hash-table :test (hash-table-test hash-table))))
                             (maphash (lambda (k v) (setf (gethash k copy) v)) hash-table)
                             copy)))
         (total (total-frequency target-table))
         (sampled-key nil))
    (loop with accumulator = 0
          for key being the hash-keys of target-table
          for freq = (gethash key target-table)
          do (incf accumulator freq)
          when (> accumulator r)
            do (setf sampled-key key)
               (remhash key target-table)
               (return))
    (if modify-original
        sampled-key
        (values sampled-key target-table))))

;; Wrapper for easy mode selection
(defun weighted-sample (hash-table &key (replacement t) (modify-original t))
  "Sample an item from a frequency hash table. Use :REPLACEMENT NIL for no repeats; :MODIFY-ORIGINAL NIL to keep the input table intact."
  (if replacement
      (sample-with-replacement hash-table)
      (sample-without-replacement hash-table :modify-original modify-original)))

Example Usage #

;; Create a sample frequency hash table
(defparameter *my-histogram* (make-hash-table :test 'equal))
(setf (gethash "apple" *my-histogram*) 3
      (gethash "banana" *my-histogram*) 5
      (gethash "cherry" *my-histogram*) 2)

;; With replacement sampling (can return duplicates)
(sample-with-replacement *my-histogram*) ; Might return "banana" most often

;; Without replacement (modifies original table)
(weighted-sample *my-histogram* :replacement nil) ; Removes the sampled item from *my-histogram*

;; Non-destructive without replacement
(multiple-value-bind (sampled remaining-table)
    (weighted-sample *my-histogram* :replacement nil :modify-original nil)
  (format t "Sampled: ~a~%Remaining items: ~a" sampled (alexandria:hash-table-alist remaining-table)))

Bulk Without-Replacement Sampling #

If you need to draw multiple unique samples, use this helper:

(defun sample-n-without-replacement (hash-table n &key (modify-original t))
  "Draw N unique samples from the hash table. Returns a list of samples + remaining table (if non-destructive)."
  (let* ((target-table (if modify-original
                           hash-table
                           (let ((copy (make-hash-table :test (hash-table-test hash-table))))
                             (maphash (lambda (k v) (setf (gethash k copy) v)) hash-table)
                             copy)))
         (samples nil))
    (loop repeat n
          while (> (hash-table-count target-table) 0)
          do (push (sample-without-replacement target-table :modify-original t) samples))
    (if modify-original
        (nreverse samples)
        (values (nreverse samples) target-table))))

内容的提问来源于stack exchange，提问作者MadPhysicist