Ответ 1

При копировании каждой строки файла на выход оцените его вероятность того, что он должен быть удален. Первая строка должна иметь шанс на удаление 3,609,739/158,609,739. Если вы создаете случайное число от 0 до 1, и это число меньше этого отношения, не копируйте его на выход. Теперь шансы на вторую линию составляют 3,609,738/158,609,738; если эта строка не удалена, коэффициенты для третьей строки составляют 3,609,738/158,609,737. Повторяйте до конца.

Поскольку коэффициенты изменяются при обработке каждой строки, этот алгоритм гарантирует точное количество строк. После того, как вы удалили 3,609,739, шансы равны нулю; если в любой момент вам нужно будет удалить каждую оставшуюся строку в файле, шансы перейдут к одному.

Ответ 2

Вы всегда можете заранее генерировать номера строк (список из 3 609 739 случайных чисел, выбранных без замены), которые вы планируете удалить, а затем просто перебирать файл и копировать в другой, пропуская строки по мере необходимости. Если у вас есть место для нового файла, это сработает.

Вы можете выбрать случайные числа с random.sample Например.

random.sample(xrange(158609739), 3609739)

Ответ 3

Доказательство ответа Ransom Mark

Пусть проще использовать номера (по крайней мере для меня!):

• 10 элементов
• удалить 3 из них

В первый раз через цикл мы предположим, что первые три элемента удаляются - вот как выглядят вероятности:

• первый элемент: 3/10 = 30%
• второй элемент: 2/9 = 22%
• третий элемент: 1/8 = 12%
• четвертый элемент: 0/7 = 0%
• пятый элемент: 0/6 = 0%
• шестой элемент: 0/5 = 0%
• седьмой элемент: 0/4 = 0%
• восьмой элемент: 0/3 = 0%
• девятый элемент: 0/2 = 0%
• Десятый элемент: 0/1 = 0%

Как вы можете видеть, когда он достигает нуля, он остается равным нулю. Но что, если ничего не удаляется?

• первый элемент: 3/10 = 30%
• второй элемент: 3/9 = 33%
• третий элемент: 3/8 = 38%
• четвертый элемент: 3/7 = 43%
• пятый элемент: 3/6 = 50%
• шестой элемент: 3/5 = 60%
• седьмой элемент: 3/4 = 75%
• восьмой элемент: 3/3 = 100%
• девятый элемент: 2/2 = 100%
• десятый элемент: 1/1 = 100%

Таким образом, хотя вероятность зависит от каждой строки, в целом вы получаете результаты, которые вы ищете. Я сделал еще один шаг и закодировал тест на Python на миллион итераций в качестве последнего доказательства для себя - удалите семь элементов из списка из 100:

# python 3.2
from __future__ import division
from stats import mean  # http://pypi.python.org/pypi/stats
import random

counts = dict()
for i in range(100):
    counts[i] = 0

removed_failed = 0

for _ in range(1000000):
    to_remove = 7
    from_list = list(range(100))
    removed = 0
    while from_list:
        current = from_list.pop()
        probability = to_remove / (len(from_list) + 1)
        if random.random() < probability:
            removed += 1
            to_remove -= 1
            counts[current] += 1
    if removed != 7:
        removed_failed += 1

print(counts[0], counts[1], counts[2], '...',
      counts[49], counts[50], counts[51], '...',
      counts[97], counts[98], counts[99])
print("remove failed: ", removed_failed)
print("min: ", min(counts.values()))
print("max: ", max(counts.values()))
print("mean: ", mean(counts.values()))

и здесь результаты одного из нескольких раз я его запускал (все они были похожи):

70125 69667 70081 ... 70038 70085 70121 ... 70047 70040 70170
remove failed:  0
min:  69332
max:  70599
mean:  70000.0

Последнее замечание: Python random.random() - [0.0, 1.0) (не включает в себя 1.0 как возможность).

Ответ 4

Я считаю, что вы ищете "Алгоритм S" из раздела 3.4.2 Кнута (DE Knuth, The Art of Computer Programming) Том 2: Семинумерический Алгоритмы, второе издание. Addison-Wesley, 1981).

Вы можете увидеть несколько реализаций в http://rosettacode.org/wiki/Knuth%27s_algorithm_S

В списке Perlmonks есть некоторые реализации Perl алгоритма S и алгоритма R, которые также могут оказаться полезными.

Эти алгоритмы полагаются на содержательную интерпретацию чисел с плавающей запятой, таких как 3609739/158609739, 3609738/158609738 и т.д., которые могут не иметь достаточного разрешения со стандартным типом Float, если только тип данных Float не реализован с использованием номера двойная точность или больше.

Ответ 5

Здесь возможно решение с использованием Python:

import random

skipping = random.sample(range(158609739), 3609739)

input = open(input)
output = open(output, 'w')

for i, line in enumerate(input):
    if i in skipping:
        continue
    output.write(line)

input.close()
output.close()

Здесь другой метод Mark:

import random

lines_in_file = 158609739
lines_left_in_file = lines_in_file
lines_to_delete = lines_in_file - 155000000

input = open(input)
output = open(output, 'w')

try:
    for line in input:
        current_probability = lines_to_delete / lines_left_in_file
        lines_left_in_file -= 1
        if random.random < current_probability:
            lines_to_delete -= 1
            continue
        output.write(line)
except ZeroDivisionError:
    print("More than %d lines in the file" % lines_in_file)
finally:
    input.close()
    output.close()

Ответ 6

Я написал этот код, прежде чем увидеть, что Даррен Инь выразил свой принцип.

Я изменил свой код, чтобы использовать имя skipping (я не решался выбрать kangaroo...) и ключевое слово continue из Этана Фурмана, чей кодовый принцип тоже.

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

import random
import os.path

def spurt(ff,skipping):
    for i,line in enumerate(ff):
        if i in skipping:
            print 'line %d excluded : %r' % (i,line)
            continue
        yield line

def randomly_reduce_file(filepath,nk = None,
                         d = {0:'st',1:'nd',2:'rd',3:'th'},spurt = spurt,
                         sample = random.sample,splitext = os.path.splitext):

    # count of the lines of the original file
    with open(filepath) as f:  nl = sum(1 for _ in f)

    # asking for the number of lines to keep, if not given as argument
    if nk is None:
        nk = int(raw_input('  The file has %d lines.'
                           '  How many of them do you '
                           'want to randomly keep ? : ' % nl))

    # transfer of the lines to keep,
    # from one file to another file with different name
    if nk<nl:
        with open(filepath,'rb') as f,\
             open('COPY'.join(splitext(filepath)),'wb') as g:
            g.writelines(  spurt(f,sample(xrange(0,nl),nl-nk) )  )
            # sample(xrange(0,nl),nl-nk) is the list
            # of the counting numbers of the lines to be excluded 
    else:
        print '   %d is %s than the number of lines (%d) in the file\n'\
              '   no operation has been performed'\
              % (nk,'the same' if nk==nl else 'greater',nl)

Ответ 7

С переменной $RANDOM вы можете получить случайное число от 0 до 32 767.

С этим вы можете читать в каждой строке и видеть, меньше ли $RANDOM меньше 155,000,000 / 158,609,739 * 32,767 (это 32 021), и если да, пусть строка проходит.

Конечно, это не даст вам ровно 150 000 000 строк, но довольно близко к нему в зависимости от нормальности генератора случайных чисел.

РЕДАКТИРОВАТЬ: Ниже приведен код для запуска:

#!/bin/bash
while read line; do
  if (( $RANDOM < 32021 ))
  then
    echo $line
  fi
done

Назовите его так:

thatScript.sh <inFile.txt >outFile.txt