Получение большого (1 миллиона) количества подстрок (шириной 100 символов) из длинной строки (3 миллиона символов) - PullRequest
Новая
       28

Получение большого (1 миллиона) количества подстрок (шириной 100 символов) из длинной строки (3 миллиона символов)

2 голосов
/ 21 марта 2012

Как я могу эффективно взять 1 миллион подстрок из строки с более чем 3 миллионами символов в C #? Я написал программу, которая включает чтение случайных чтений ДНК (подстрок из случайной позиции) длиной, скажем, 100 из строки с 3 миллионами символов. Есть 1 миллион таких чтений. В настоящее время я запускаю цикл while, который выполняется 1 миллион раз, и читаю подстроку длиной 100 символов из строки с 3 миллионами символов. Это занимает много времени. Что я могу сделать, чтобы завершить это быстрее?

вот мой код, len - длина исходной строки, в данном случае 3 миллиона, это может быть всего 50, поэтому проверка в цикле while. 

while(i < 1000000 && len-100> 0) //len is 3000000
            {
                int randomPos = _random.Next()%(len - ReadLength);
                readString += all.Substring(randomPos, ReadLength) + Environment.NewLine;
                i++;


            }

Ответы [ 4 ]

2 голосов
/ 21 марта 2012

Использование StringBuilder для сборки строки даст вам увеличение обработки в 600 раз (так как это предотвращает повторное создание объекта каждый раз, когда вы добавляете строку.

перед циклом (инициализация емкости позволяет избежать воссоздания резервного массива вStringBuilder): 

StringBuilder sb = new StringBuilder(1000000 * ReadLength);

в цикле: 

sb.Append(all.Substring(randomPos, ReadLength) + Environment.NewLine);

после цикла: 

readString = sb.ToString();

Использование массива char вместо строки для извлечения значений приводит к другому30% улучшение, поскольку вы избегаете создания объекта при вызове Substring ():

перед циклом: 

char[] chars = all.ToCharArray();

в цикле: 

sb.Append(chars, randomPos, ReadLength);
sb.AppendLine();

Редактировать (окончательная версия, которая не использует StringBuilder и выполняется за 300 мс): 

char[] chars = all.ToCharArray();    
var iterations = 1000000;
char[] results = new char[iterations * (ReadLength + 1)];    
GetRandomStrings(len, iterations, ReadLength, chars, results, 0);    
string s = new string(results);

private static void GetRandomStrings(int len, int iterations, int ReadLength, char[] chars, char[] result, int resultIndex)
{
    Random random = new Random();
    int i = 0, index = resultIndex;
    while (i < iterations && len - 100 > 0) //len is 3000000 
    {
        var i1 = len - ReadLength;
        int randomPos = random.Next() % i1;

        Array.Copy(chars, randomPos, result, index, ReadLength);
        index += ReadLength;
        result[index] = Environment.NewLine[0];
        index++;

        i++;
    }
}
1 голос
/ 21 марта 2012

Я думаю, что найдутся лучшие решения, но экземпляры класса .NET StringBuilder быстрее, чем экземпляры класса String, потому что он обрабатывает данные как поток.

Вы можете разбить данные на части и использовать .NET Task Parallel Library для многопоточности и параллелизма

Редактировать: назначить фиксированные значения переменной вне цикла, чтобы избежать пересчета; 

int x = len-100 
int y = len-ReadLength

использовать 

StringBuilder readString= new StringBuilder(ReadLength * numberOfSubStrings);
readString.AppendLine(all.Substring(randomPos, ReadLength));

для параллелизма вы должны разделить ваш ввод на части. Затем запустите эти операции на куски в отдельных потоках. Затем объедините результаты.

Важно: Как показал мой предыдущий опыт, эти операции выполняются быстрее с .NET v2.0, а не с v4.0, поэтому вам следует изменить целевую версию платформы проекта; но вы не можете использовать Task Parallel Library с .NET v2.0, поэтому вы должны использовать многопоточность oldschool, как 

Thread newThread ......
0 голосов
/ 21 марта 2012

Как долго это долго? Это не должно быть так долго. 

var file = new StreamReader(@"E:\Temp\temp.txt");
var s = file.ReadToEnd();
var r = new Random();
var sw = new Stopwatch();
sw.Start();
var range = Enumerable.Range(0,1000000);
var results = range.Select( i => s.Substring(r.Next(s.Length - 100),100)).ToList();
sw.Stop();
sw.ElapsedMilliseconds.Dump();
s.Length.Dump();

Итак, на моей машине результат составил 807 мс, а строка - 4 055 442 символа.

Редактировать: я только что заметил, что вы хотите строку в результате, поэтому мое решение выше просто меняется на ... 

var results = string.Join(Environment.NewLine,range.Select( i => s.Substring(r.Next(s.Length - 100),100)).ToArray());

И добавляет около 100 мс, так что в общей сложности все равно меньше секунды.

0 голосов
/ 21 марта 2012

Редактировать: Я отказался от идеи использовать memcpy, и я думаю, что результат супер. Я разбил строку длиной 3 метра на 30 строк длиной 100 штук каждая за 43 миллисекунды. 

private static unsafe string[] Scan(string hugeString, int subStringSize)
{
    var results = new string[hugeString.Length / subStringSize];

    var gcHandle = GCHandle.Alloc(hugeString, GCHandleType.Pinned);

    var currAddress = (char*)gcHandle.AddrOfPinnedObject();

    for (var i = 0; i < results.Length; i++)
    {
        results[i] = new string(currAddress, 0, subStringSize);
        currAddress += subStringSize;
    }

    return results;
}

Чтобы использовать метод для случая, показанного в вопросе: 

const int size = 3000000;
const int subSize = 100;

var stringBuilder = new StringBuilder(size);
var random = new Random();

for (var i = 0; i < size; i++)
{
    stringBuilder.Append((char)random.Next(30, 80));
}

var hugeString = stringBuilder.ToString();

var stopwatch = Stopwatch.StartNew();
for (int i = 0; i < 1000; i++)
{
    var strings = Scan(hugeString, subSize);
}
stopwatch.Stop();

Console.WriteLine(stopwatch.ElapsedMilliseconds / 1000); // 43
...