Разделение строки без строки. Разделение

Question

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

Ниже приведен рабочий код, который я придумал.

Я хотел бы знать, как я могу улучшить время работы до O (n)?

Также приветствуются любые предложения по улучшению.

public static string[] split(string txt, char[] delim)
{
    char[] text = txt.ToCharArray();
    string[] result = new string[0];
    int count = 0;
    int i = 0;
    StringBuilder buff = new StringBuilder(); 
    while(i < text.Length)
    {
        bool found = false;
        foreach(char del in delim)
        {
            if(del == txt[i])
            {
                found = true;
                break;
            }
        }
        if(found)
        {
            count++;
            Array.Resize(ref result, count);
            result[count - 1] = buff.ToString();
            buff = new StringBuilder();                 
        }
        else
        {
            buff.Append(txt[i]);
        }

        i++;
    }

    if(buff.Length != 0)
    {
        count++;
        Array.Resize(ref result, count);
        result[count - 1] = buff.ToString();
    }

    return(result);
}

Answer 1

У меня есть несколько изменений, которые одновременно сделают эту функцию более похожей на C и сократят время выполнения до O (n):

1) Вместо того, чтобы динамически изменять размер массива result много раз, выследует создать его с достаточным количеством мест для хранения максимального количества строк (вы знаете, что это число меньше txt.Length), а затем изменить его размер только один раз в самом конце, прежде чем вернуть его.

2) Вместо сборкиваши результаты с StringBuilder, создайте char[] buff длины txt.Length и индексную переменную j и сделайте buff[j++] = txt[i].

Я думаю, что ваша функция должна быть O (N) после того, как вы это сделаете.Технически, это будет O (N * M), где M - количество разделителей.

EDIT 1:

Вот изменение, которое сделает его O(N) + O (M) вместо O (N * M):

Вместо циклического обхода разделителей для каждого символа в строке, вы должны циклически проходить через разделители в ADVANCE и устанавливать массив какthis:

bool[] isDelimiter = new bool[128];  // increase size if you are allowing non-ascii
foreach(char delim in isDelimiter)
{
    isDelimiter[(int)char] = true;
}

Тогда вы можете просто использовать этот массив для проверки каждого символа строки в постоянном времени.

Answer 2

Я думаю, ваш профессор ищет API, который принимает только один символ, а не массив.Не массив символов.Под этим я подразумеваю, что если в качестве разделительной строки указано «abcd», вы не будете разбивать на все экземпляры «a», «b», «c», «d».Вы разделитесь, только если найдете всю строку.

Ваш текущий алгоритм не O (n), потому что для каждого элемента входного массива вы сравниваете его с каждым элементом массива-разделителя.Это приводит к времени выполнения O (n * m).

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

public static String[] Split(String input, String delimiter)
{
    List<String> parts = new List<String>();
    StringBuilder buff = new StringBuilder();
    if (delimiter.Length > 1) //you are splitting on a string not a character
    {
       //perform string searching algorithm here
    }
    else if(delimiter.Length == 0)
    {
       throw new InvalidOperationException("Invalid delimiter.");
    }
    else //you are splitting on a character
    {
       char delimChar = delimiter[0];
       for (int i = 0; i < input.Length; i++)
       {
           if (input[i] == delimChar)
           {
               parts.Add(buff.ToString());
               buff.Clear();
           }
           else
           {
               buff.Append(input[i]);
           }
       }
    }
    return parts.ToArray();
}

C # String.Split() действительно принимает массив разделителей, но я не верю, что это делаетрасщепление по времени O (n).

Если вы ищете алгоритмы поиска строк, они могут оказаться полезными.http://en.wikipedia.org/wiki/String_searching_algorithm

edit: я неправильно сослался на тот факт, что API C # String.Split() не принимает массив разделителей.

Answer 3

Вы можете сделать это O (n), если поместите символы разделителя в HashSet.Проверка на наличие значения в HashSet - это O (1).

var delimterSet = new HashSet<char>(delim);

...

if(delimterSet.Contains(txt[i]) { ... }

Однако для небольшого числа разделителей это не улучшитпроизводительность.

Answer 4

Невозможно выполнить String.Split в O (n), так как список разделителей должен быть пройден / обыскан.

Answer 5

Может быть, вы можете попробовать сделать всю работу за один раз

public static String[] Split(String txt, char[] delim)
{
    if (txt == null)
        return new String[0]; // or exception
    if (delim == null || delim.Length == 0)
        return new String[0]; // or exception

    char[] text = txt.ToCharArray();
    string[] result = new string[1]; // If there is no delimiter in the string, return the whole string
    int part = 0;
    int itemInArray = 1;

    for (int i = 0; i < text.Length; i++)
    {
        if (IsIn(delim, text[i]))
        {
            Array.Resize(ref result, ++itemInArray); // Is it consider as a framework method ???
            part++;
        }
        else
            result[part] += text[i];
    }
    return result;
}
public static Boolean IsIn(char[] delim, char c)
{
    for (int i = 0; i < delim.Length; i++)
        if (c == delim[i])
            return true;
    return false;
}