相关疑难解决方法(0)

我有一个10 ^ 7行文件,其中我想从文件中随机选择1/100行.这是我所拥有的AWK代码,但它会预先包含所有文件内容.我的PC内存无法处理这样的问题.还有其他办法吗？

awk 'BEGIN{srand()}
!/^$/{ a[c++]=$0}
END {  
  for ( i=1;i<=c ;i++ )  { 
    num=int(rand() * c)
    if ( a[num] ) {
        print a[num]
        delete a[num]
        d++
    }
    if ( d == c/100 ) break
  }
 }' file

我正在尝试编写一种算法,该算法可以随机地从序列中选择N个不同的项目,而不需要事先知道序列的大小,并且在不止一次迭代序列的情况下进行迭代是很昂贵的.例如,序列的元素可能是一个巨大文件的行.

我在N = 1时找到了一个解决方案(也就是说,当试图从一个巨大的序列中随机选择一个元素时):

import random
items = range(1, 10) # Imagine this is a huge sequence of unknown length
count = 1
selected = None
for item in items:
    if random.random() * count < 1:
        selected = item
    count += 1

但是如何才能为其他N值(比如N = 3)实现同样的目的呢？

我是编程的初学者，我正在寻找如何生成满足条件的三个整数的好主意。

例子：

给定n = 30，我们被要求生成三个整数 a、b 和 c，因此7*a + 5*b + 3*c = n。我尝试使用for循环，但它花费了太多时间，而且我的最大测试时间为 1000 毫秒。

我正在使用 Python 3。

我的尝试：

x = int(input())
c = []
k = []
w = []
for i in range(x):
    for j in range(x):
        for h in range(x):
           if 7*i + 5*j + 3*h = x:
              c.append(i)
              k.append(j)
              w.append(h)
if len(c) == len(k) == len(w) 
    print(-1)
else: 
    print(str(k[0]) + ' ' + str(c[0]) + ' ' + str(w[0]))

说我有一个长度数字的链表N.N非常大,我事先并不知道确切的价值N.

如何最有效地编写一个从列表中返回k完全随机数的函数？

是否可以在常量堆栈和堆空间中在State monad中执行折叠？或者是一种不同的功能技术更适合我的问题？

接下来的部分将描述问题和激励用例.我正在使用Scala,但Haskell中的解决方案也受到欢迎.

折叠在StateMonad填充堆

假设Scalaz 7.考虑一下州Monad的monadic折叠.为了避免堆栈溢出,我们将蹦蹦跳跳.

import scalaz._
import Scalaz._
import scalaz.std.iterable._
import Free.Trampoline

type TrampolinedState[S, B] = StateT[Trampoline, S, B] // monad type constructor

type S = Int  // state is an integer
type M[B] = TrampolinedState[S, B] // our trampolined state monad

type R = Int  // or some other monoid

val col: Iterable[R] = largeIterableofRs() // defined elsewhere

val (count, sum): (S, R) = col.foldLeftM[M, R](Monoid[R].zero){ 
    (acc: R, x: R) => StateT[Trampoline, S, R] { …

这是一个面试饼干的问题 -

鉴于您正在以恒定速率从仪器接收样本,并且您有恒定的存储空间,您将如何设计一种存储算法,使我能够获得有代表性的数据读取,无论何时查看它？换句话说,代表了迄今为止系统的行为.

我无法理解它.所以,我正在寻找想法.