“无法分配8192个字节”。这个错误是什么？它为什么会发生？ [英] "Could not allocate 8192 bytes". What is this error and why does it occur?

问题描述

我正在尝试对字符串进行示例性问题，其中我将字符串作为输入并找出每个后缀与其自身的相似性。



对于两个字符串A和B，字符串的相似性是两个字符串共有的最长前缀的长度。例如，字符串abc和abd的相似性为2，而字符串aaa和aaab的相似度为3.



例如，如果输入字符串是ababaa。然后它的后缀是ababaa，babaa，abaa，baa，aa，a。相应的相似之处将是6,0,3,0,1,1。它们被添加并打印在控制台上。



现在在我的问题中，我'' m如下输入。第一行是必须打印相似之和（每个后缀）的字符串数。在下一行中，我输入了许多字符串。我已经为这个问题编写了代码，它正常运行正常。但是当我给出一个非常大的字符串时，它会给出以下运行时异常消息无法分配8192个字节。我的代码如下

Hi, I''m trying out a sample problem on strings wherein I take a string as input and find out the similarity of each of its suffix with itself.

For two strings A and B, the similarity of the strings is the length of the longest prefix common to both strings. For example, the similarity of strings "abc" and "abd" is 2, while the similarity of strings "aaa" and "aaab" is 3.

For example, if the input string is ababaa. Then its suffixes would be ababaa, babaa, abaa, baa, aa, a. The corresponding similarities would be 6, 0, 3, 0, 1, 1. These are added and printed on the console.

Now in my problem, I''m taking input as follows. First line is the number of strings whose sum of similarities (with each of it''s suffixes) have to be printed. In the next lines, I enter that many number of strings. I have written code for the problem and it is running fine for normal inputs. But when i give a very large string, it is giving the following runtime exception message "Could not allocate 8192 bytes". My code is as follows

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static List<int> listOfSimilarities = new List<int>();
    static void Main(String[] args) {
        
        int t = 0;
        
        t = Convert.ToInt32(Console.ReadLine());
        
        if( t >= 1 && t <=10)
        {
            
            List<string> listOfStrings = new List<string>();
            string input = string.Empty;
            
            for(int i = 1 ; i <= t ; i++)
            {
                
                input = Console.ReadLine().ToString();
                if(input.Length < 100000)
                {
                    listOfStrings.Add(input);
                }
            }
            
            foreach(string str in listOfStrings)
            {
                List<string> listOfSuffixes = new List<string>();
                listOfSuffixes = GetSuffixes(str);
                
                List<int> listOfSimilaritiesForEachSuffix = new List<int>();
                listOfSimilaritiesForEachSuffix = GetSimilaritiesWithString(str, listOfSuffixes);
                
                int sumOfSimilarities = GetSumOfSimilarities(listOfSimilaritiesForEachSuffix);
                
                listOfSimilarities.Add(sumOfSimilarities);
                
            }
            
            foreach(int similarity in listOfSimilarities)
            {
                Console.Write(similarity + "\n");
            }
        }
    }
    
static int GetSumOfSimilarities(List<int> listOfSimilaritiesForEachSuffix)
    {
        int result = 0;
        foreach(int i in listOfSimilaritiesForEachSuffix)
        {
            result += i;
        }
        return result;
    }
    
static List<int> GetSimilaritiesWithString(string str, List<string> listOfSuffixes)
    {
        List<int> listOfSimilaritiesForEachSuffix = new List<int>();
        char[] arrayOfActualString = str.ToCharArray();
        foreach(string suffix in listOfSuffixes)
        {
            int count = 0;
            char[] suffixArray = suffix.ToCharArray();
            for(int i = 0; i < suffixArray.GetLength(0) ; i++)
            {
                if(suffixArray[i] == arrayOfActualString[i])
                {
                    count++;
                }
                else
                {
                    break;
                }
            }
            listOfSimilaritiesForEachSuffix.Add(count);
        }
        return listOfSimilaritiesForEachSuffix;
    }
    
static List<string> GetSuffixes(string str)
    {
        List<string> listOfSuffixes = new List<string>();
        for(int i = 0; i < str.Length ; i++)
        {
            listOfSuffixes.Add(str.Substring(i));
        }
        return listOfSuffixes;
    }
}

想知道为什么会发生这种情况吗？

Any idea as to why this is happening?

推荐答案

当我用99,999个字节字符串运行你的代码（我被欺骗并从文件中读取）时，我在第一次运行GetSuffixes时得到超出系统内存，所以首先看一下 - 我们找到了什么？



输入字符串长度：99,999字节。 我是8,847，所以它不会接近字符串的末尾。



查看代码：每次都创建并存储一个字符串，比前一个字符短一个字符。所以用子串创建的字符串是：

99999字符

99998字符

99997字符

...

因此，当您收到错误时，您已直接分配845,652,024个字符，每个字符两个字节（unicode）或1.6 GB字符串空间。再加上每个字符串的Object开销，以及用于存储引用的List空间，当它开始出现问题时你会感到惊讶吗？



我强烈建议你回到算法中的一两个阶段，再想一想你应该怎么做。

When I run your code with 99,999 byte strings (I cheated and read it from a file) I get "out of system memory" on the first run through GetSuffixes, so start by looking at that - and what do we find?

Input string length: 99,999 bytes. "i" is 8,847, so it doesn''t get near the end of the string.

Look at the code: each time round, you create and store a string which is one character shorter than the previous one. So the strings you create with Substring are:
99999 chars
99998 chars
99997 chars
...
So by the time you get the error, you have directly allocated 845,652,024 characters, each of two bytes (unicode), or 1.6 GB in string space. Add to that the Object overhead for each string, and the List space you are using to store the references, and you are surprised when it starts to have problems?

I strongly suggest that you go back a stage or two in your algorithm, and think again about exactly how you should do this.

不是在列表对象中存储所有子字符串（后缀），而是计算每个后缀的相似度之和。我无法弄清楚你计算相似度之和的目的。如果有帮助，您可以查看KMP故障功能。

Instead of storing all sub-strings (suffixes) in list object, calculate the sum of similarities for each suffix. I could not figure out your purpose of calculating the sum of similarity. You can look into KMP failure function if that helps.

这篇关于“无法分配8192个字节”。这个错误是什么？它为什么会发生？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！