louai · HackerTrans

3 года назадdiscuss

ChatGPT 4

> Use reservoir sampling to get 100 random lines from a dictionary that doesn’t fit into memory. Give me an implementation in Python.

> Reservoir sampling is a great choice for randomly selecting a fixed number of items from a stream of unknown size, especially when the entire dataset cannot fit into memory. Here's a Python implementation for selecting 100 random lines from a large file, like a dictionary, using reservoir sampling:

  ```python
  import random

  def reservoir_sampling(file_name, k):
      reservoir = []
      with open(file_name, 'r') as file:
          for i, line in enumerate(file):
              if i < k:
                  # Fill the reservoir array
                  reservoir.append(line.strip())
              else:
                  # Randomly replace elements in the reservoir
                  # with a decreasing probability.
                  # Choose an integer between 0 and i (inclusive)
                  j = random.randint(0, i)
                  if j < k:
                      reservoir[j] = line.strip()
      return reservoir

  # Example usage
  file_path = 'path_to_your_large_file.txt'  # Replace with your file path
  sampled_lines = reservoir_sampling(file_path, 100)
  print(sampled_lines)
  ```

> This script opens a file and reads through it line by line. For the first 100 lines, it adds them directly to the reservoir. For each subsequent line, it randomly decides whether to replace an existing line in the reservoir with the new line. The probability of replacing decreases as it progresses through the file, ensuring each line has an equal chance of being included in the final sample.

louai

5 лет назадdiscuss

With Lisp-2 designs as discussed in the article this is not an issue, as variables and functions are in different namespaces:

  CL-USER> (defun foo (list) (list list))
  FOO
  CL-USER> (foo 42)
  (42)

In this case the function attached to the symbol LIST is applied to the argument with the same name, but that isn't a problem.

To further illustrate, in the above example the LIST symbol is imported from the package COMMON-LISP and has a function, plist etc. attached to it:

  CL-USER> (symbol-package 'list)
  #<PACKAGE "COMMON-LISP">
  CL-USER> (symbol-function 'list)
  #<FUNCTION LIST>
  CL-USER> (symbol-plist 'list)
  NIL

louai

5 лет назадdiscuss

Macro expansion is done in the host environment, not the target environment. You can compile the macro definition to a function taking a form and an environment. This would be something you arrange for within your compiler.

CLTL2 specifies a function `parse-macro ` which is available in most implementations. Portably you can call it using the `trivial-cltl2` package:

https://github.com/Zulu-Inuoe/trivial-cltl2

Robert Strandh has written both papers and code for handling environments:

http://metamodular.com/SICL/environments.pdf http://metamodular.com/clostrum.pdf

louai

5 лет назадdiscuss

One correction to my post above - Corman Lisp is a Free implementation that does have the ability to produce DLLs, but it is limited to Windows:

https://github.com/sharplispers/cormanlisp/blob/master/docum...

louai

5 лет назадdiscuss

Common Lisp actually doesn't specify a mechanism for this. There are implementations that can compile to e.g. DLL:

http://www.lispworks.com/documentation/lw71/DV/html/delivery... https://franz.com/support/documentation/current/doc/dll.htm

Unfortunately none of the FOSS implementations have this ability (to my knowledge). There is nothing inherently in Common Lisp that mandates the "core dump" delivery model.

louai

5 лет назадdiscuss

A characteristic of intrusive data structures is generally good cache friendliness. In this context "intrusive" means that the data structure is embedded with the data that's being stores.

In C terms as in this case that means that the pointers required of individual nodes aren't allocated in separate structs and are instead embedded in one struct that also includes the payload.

This means that the cache behavior is improved, as a given node is stored in a single location. Once you access a node the associated data is already in the cache, instead of having to be fetched via a separate pointer dereference.

louai

5 лет назадdiscuss

Note that it says less than one character. A character in UTF-8 can be composed of multiple bytes.

The encoding scheme is laid out in the linked email. Based on the high bits it's possible to detect when a new character starts. Relevant portion:

  We define 7 byte types:
  T0 0xxxxxxx      7 free bits
  Tx 10xxxxxx      6 free bits
  T1 110xxxxx      5 free bits
  T2 1110xxxx      4 free bits
  T3 11110xxx      3 free bits
  T4 111110xx      2 free bits
  T5 111111xx      2 free bits

  Encoding is as follows.
  >From hex Thru hex      Sequence             Bits
  00000000  0000007f      T0                   7
  00000080  000007FF      T1 Tx                11
  00000800  0000FFFF      T2 Tx Tx             16
  00010000  001FFFFF      T3 Tx Tx Tx          21
  00200000  03FFFFFF      T4 Tx Tx Tx Tx              26
  04000000  FFFFFFFF      T5 Tx Tx Tx Tx Tx    32

[...]

  4. All of the sequences synchronize on any byte that is not a Tx byte.

If you are starting mid-run, skip initial Tx bytes. That will always be less than one character.

comments