Как максимально эффективно удалить любое количество лишних пробелов из строки

Question

Как можно улучшить нижеприведенный код, чтобы он работал максимально эффективно:

StringBuilder str = new StringBuilder("Lorem ipsum dolor sit amet, " +
"consectetur adipiscing elit, sed    do eiusmod tempor incididunt ut  labore et dolore magna aliqua. " +
"Ut enim ad minim veniam, quis nostrud exercitation ullamco      laboris nisi ut aliquip ex ea commodo " +
"consequat. Duis aute irure dolor in    reprehenderit in voluptate  velit esse cillum dolore eu fugiat " +
"nulla    pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt " +
"mollit anim id est  laborum.");
int endIndex = 0;
for (int i = 0; i < str.Length-1; i++)
{
    if (str[i] == ' ' && str[i+1] == ' ')
    {
        endIndex = i+1;
        for (int j = endIndex; j < str.Length-1; j++)
        {
            if (str[j + 1] != ' ')
            {
                endIndex = j;
                break;
            }
        }
        str.Remove(i, endIndex-i);
        i = endIndex - 1;
    }
}
Console.WriteLine(str);

Вы вот здесь ничего не забыли сделать? https://ru.stackoverflow.com/questions/1002701/nullreferenceexception-%d0%bf%d1%80%d0%b8-%d0%bf%d0%be%d0%bf%d1%8b%d1%82%d0%ba%d0%b5-%d0%bf%d1%80%d0%be%d0%b2%d0%b5%d1%80%d0%ba%d0%b8-%d0%be%d0%b1%d1%8a%d0%b5%d0%ba%d1%82%d0%b0-%d0%bd%d0%b0-null — , Jul 15 '19 at 15:58
ну как минимум можно удалять не на каждой итерации - а один раз в конце — Grundy, Jul 15 '19 at 16:12

tym32167 · Accepted Answer · 2019-07-15T17:35:57.263

4

Например, так

var str = "Lorem ipsum dolor sit amet, " +
"consectetur adipiscing elit, sed    do eiusmod tempor incididunt ut  labore et     dolore magna aliqua. " +
"Ut enim ad minim veniam, quis nostrud exercitation ullamco      laboris nisi ut     aliquip ex ea commodo " +
"consequat. Duis aute irure dolor in    reprehenderit in voluptate  velit esse cillum     dolore eu fugiat " +
"nulla    pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui     officia deserunt " +
"mollit anim id est  laborum.";

var sb = new StringBuilder(str.Length);
int ind = 0;
while (ind < str.Length)
{
    while (ind < str.Length && str[ind] != ' ') sb.Append(str[ind++]);
    if (ind < str.Length && str[ind] == ' ')        
        sb.Append(' ');     
    while (ind < str.Length && str[ind] == ' ') ind++;
}   
Console.WriteLine(sb.ToString());

Вывод

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

edited Jul 15 '19 at 17:35

answered Jul 15 '19 at 16:15

tym32167

32,857

Все же не забывайте, что лучше вызывать конструктор с указанием ожидаемой результирующей длины строки: new StringBuilder(str.Length). А то плодить в памяти кучу StringBuilder'ов с чанками по 16 символов - занятие нежелательное) – Kir_Antipov Jul 15 '19 at 17:26
@Kir_Antipov для этого надо было посчитать примерную длину результата, но мне было лень это делать :) – tym32167 Jul 15 '19 at 17:28
@Kir_Antipov ну, и если посчитать длину ркзультата, то можно просто массив char завести и туда нужные денные скопировать, то есть можно совсем без StringBuilder всё сделать )\ – tym32167 Jul 15 '19 at 17:30
1

Ну так длина выше, чем у первоначальной строки, не получится ведь, правильно?) А пробелы вряд ли будут занимать весомую часть текста, так что уж лучше выделить один раз немного больше памяти, нежели каждые 16 символов инициировать процесс создания нового StringBuilder'a) – Kir_Antipov Jul 15 '19 at 17:33
Касательно задачи, где результирующая строка будет <= по длине, чем заданная, работа с простым массивом символов будет на порядок быстрее, так что да, можно и без билдера вовсе) – Kir_Antipov Jul 15 '19 at 17:35
@Kir_Antipov ок, ок, добавил :) – tym32167 Jul 15 '19 at 17:36
Таки вижу, вижу :D – Kir_Antipov Jul 15 '19 at 17:37
@Kir_Antipov, откуда информация про 16 символов? Может 16К символов? – Qwertiy Jul 15 '19 at 18:12
1

@Qwertiy: из исходников. Как было в .NET Framework, так в Core и перекочевало. По умолчанию StringBuilder содержит в себе буфер из 16 символов. Как только место кончается, он создаёт новый экземпляр билдера с 16 символами и указывает ему ссылку на себя (так что это работает как односвязный список) – Kir_Antipov Jul 15 '19 at 18:14

score 4 · Answer 2 · answered Jul 16 '19 at 13:25

Производительность это хорошо, но о ней нужно думать в контексте приложения в целом. Для большинства приложений «чистка» пробелов навряд ли будет краеугольным камнем скорости выполнения. И в большинстве приложений проще ее написать с помощью регулярного выражения:

var result = Regex.Replace(str, @"\s+", " ");

Qwertiy · Answer 3 · 2019-07-15T18:53:07.317

1

Скорее всего наиболее эффективно будет как-то так: https://ideone.com/paDaPa

using System;
using System.Text;

public class Test
{
  private static string UndupSpc(string s)
  {
    var sb = new StringBuilder(s);
    int i = 1;

    for (int q=1; q<sb.Length; ++q)
      if (sb[q] != ' ' || sb[q-1] != ' ')
        sb[i++] = sb[q];

    sb.Length = i;

    return sb.ToString();
  }

  public static void Main()
  {
    var s = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed    do eiusmod tempor incididunt ut  labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco      laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in    reprehenderit in voluptate  velit esse cillum dolore eu fugiat nulla    pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est  laborum.";

    Console.WriteLine(UndupSpc(s));
  }
}

Или так: https://ideone.com/jyWSI3

using System;
using System.Text;

public class Test
{
  private static string UndupSpc(string s)
  {
    var sb = new StringBuilder(s.Length);
    int i = 1;

    sb.Append(s[0]);

    for (int q=1; q<s.Length; ++q)
      if (s[q] != ' ' || s[q-1] != ' ')
        sb.Append(s[q]);

    return sb.ToString();
  }

  public static void Main()
  {
    var s = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed    do eiusmod tempor incididunt ut  labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco      laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in    reprehenderit in voluptate  velit esse cillum dolore eu fugiat nulla    pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est  laborum.";

    Console.WriteLine(UndupSpc(s));
  }
}

edited Jul 15 '19 at 18:53

answered Jul 15 '19 at 18:09

Qwertiy

123,725

Кстати, хочу Вас расстроить: конструктор, который использует строку, плюет на ее длину и использует емкость по умолчанию ¯\(ツ)/¯ – Kir_Antipov Jul 15 '19 at 18:23
(А, не доглядел. Он потом все таки меняет значение по умолчанию на длину строки) – Kir_Antipov Jul 15 '19 at 18:26
@Kir_Antipov, ну при том, что он копирует строку себе в буфер, вряд ли он берёт длину меньше. А вот другой баг у меня там был - я забыл хвост строки удалить - исправил. – Qwertiy Jul 15 '19 at 18:46
1

@Kir_Antipov, а вообще да, нет смысла сразу копировать строку, если я её всё равно потом переписываю. С другой стороны, было присваивание, а стал вызов Append, который внутри всякую муть может делать - тут надо проверять, что быстрее. Дополнил ответ. – Qwertiy Jul 15 '19 at 18:53
Почему ты думаешь, что это будет эффективней варианта из моего ответа? :) – tym32167 Jul 15 '19 at 18:54
@tym32167, мне кажется, они будут примерно одинаковые. Было бы хорошо замерить. Но мне кажется, версия без Append будет быстрее версии с Append :) – Qwertiy Jul 15 '19 at 18:58
я замерил все версии, даже ту, что без StringBuilder, а просто с массивом, они все примерно одинаковые. Двже версия, где StringBuilfer создаётся без начальной длины, один фиг не сильно проседает по производителности на данных из вопроса. – tym32167 Jul 15 '19 at 19:00
@tym32167, вообще, я делаю по 2 проверки на каждый символ (длина и сравнение с пробелом) плюс по одной дополнительной проверке на каждый пробел. Я сейчас посмотрел твой код внимательнее и мне кажется, что получится почти то же самое, но для групп символов, так что возможно, твоё будет быстрее. – Qwertiy Jul 15 '19 at 19:00
@tym32167, ну надо на данных покрупнее проверять. – Qwertiy Jul 15 '19 at 19:01
мне просто уже некогда проверять, но я думаю, сама асимптотика будет одна и та же – tym32167 Jul 15 '19 at 19:02
@tym32167, а где версия с массивом? Я сначала хотел через массив сделать, но я не знаю, как из куска массива создать строку, чтобы не копировать всё в промежуточный массив. Впрочем, не уверен, не может ли новый Span помочь - возможно, его уже приделали к конструкторам строк? – Qwertiy Jul 15 '19 at 19:02
@tym32167, да, асимптотика линейная у всех решений. Кроме того, которое в вопросе - там квадратичная. – Qwertiy Jul 15 '19 at 19:03
версия с массивом - там сначала вычисляю длину массива, потом массив заполняю, потом создаю строку (внутри строки массив копируется, конечно). – tym32167 Jul 15 '19 at 19:05
Давайте продолжим обсуждение в чате. – Qwertiy Jul 15 '19 at 19:25

score -1 · Answer 4 · answered Sep 17 '23 at 13:21

Только пробелы? Я пакую "простыни" для передачи по сети на SQL сервер вот так:

    private static string GetTrimmStr(string s)
    {
        if (string.IsNullOrEmpty(s)) { return ""; }
        string[] separs = new string[] { " ", "\t", "\n" };
        string[] arrspl = s.Split(separs, StringSplitOptions.RemoveEmptyEntries);
        int icnt = arrspl.Length;
        if (icnt == 0) { return ""; }
        var arrout = new string[2*icnt-1];
        arrout[0] = arrspl[0];
        for (int i=1; i<icnt; i++)
        {
            arrout[2*i-1] = " ";
            arrout[2*i] = arrspl[i];
        }
        return string.Concat(arrout);
    }

Перед конкатенацией еще комментарии удаляются, но это уже "другая история".

данный код к "максимально эффективно" не имеет никакого отношения. — Exploding Kitten, Sep 17 '23 at 15:15

Как максимально эффективно удалить любое количество лишних пробелов из строки

4 Answers4

Linked