Найдите первый неповторный символ в строке

ETag аналогичен заголовку Last-Modified. Это механизм определения изменений клиентом.

Возможно, ETag, который ПРОСТО является датой последнего изменения (т.е. тот же текст), соответствует всем критериям, необходимым для ETag. Оно просто должно быть уникальным значением, представляющим состояние ресурса. Не является уникальным во всей области ресурсов, просто в пределах ресурса.

Технически ETag имеет «бесконечное» разрешение по сравнению с заголовком Last-Modified. Последнее изменение (Last Modified) - изменяется только при степени детализации 1 секунда, тогда как ETag может быть подсекундой.

Вы можете реализовать как ETag, так и Last-Modified, или просто то или иное (или нет, конечно). Если последнего изменения недостаточно, рассмотрим ETag.

Я бы не стал устанавливать ETag для «каждого» ресурса. В основном, я не стал бы устанавливать его для чего-либо, что не ожидало бы кэширования (динамическое содержимое особенно). В этом деле нет смысла, просто потраченная впустую работа.

Edit: Я вижу вашу редакцию и уточняю.

MD5 в порядке. Единственный минус - это расчет MD5 все время. Выполнение MD5 на, скажем, 200K PDF-файле, дорого. Выполнение MD5 на ресурсе, который не ожидает кэширования, просто расточительно (т.е. динамическое содержимое).

Хитрость заключается просто в том, что какой бы механизм вы ни использовали, он должен быть таким же дешевым, каким обычно является Last-Modified. Last-Modified снова, как правило, свойство ресурса, и, как правило, очень дешево для доступа.

ETags должны быть столь же дешевыми. Если вы используете MD5, и вы можете кэшировать/хранить связь между ресурсом и MD5 хэшем, то это прекрасное решение. Однако пересчет MD5 каждый раз при необходимости ETag в основном противоречит идее использования ETags для повышения общей производительности сервера.

MVC2 имеет концепцию областей, которые создают разобщенность. Мне до сих пор не нравится, как это реализуется. Я создаю отдельный проект практически для каждого контроллера. Таким образом, я могу смешивать и сопоставлять контроллеры в новых проектах, над которыми я работаю. Отличный пример - у меня есть проект под названием «Безопасность», который обрабатывает все процессы входа в систему и управления пользователями. Другой проект, который у меня есть, называется Notification, который обрабатывает все сообщения и сообщения электронной почты. Что я делаю, чтобы собрать эти вместе, так это я создаю основной проект для любого проекта, над которым я работаю, а затем я импортирую в DLL из другого проекта, и все, что я должен убедиться, что у меня есть виды и javascript на месте, и это будет работать.

Почему бы не использовать структуру данных на основе кучи, например очередь с минимальным приоритетом. При чтении каждого символа из последовательности добавьте его в очередь с приоритетом на основе расположения в последовательности и количества вхождений. Можно изменить очередь, добавив приоритеты при столкновении, чтобы приоритет символа был суммой числовых образов этого символа. В конце цикла,первый элемент в очереди будет наименее частым символом в строке, и если имеется несколько символов со счетом = = 1, первый элемент был первым уникальным символом, добавленным в очередь.

Я бы сказал, что Gearman лучше для постановки в очередь «заданий», а RabbitMQ лучше для постановки в очередь «данных». Конечно, они оба действительно одно и то же, но то, как это работает для меня, это то, что если вы пытаетесь «фанатизировать» работу, которая должна быть выполнена, и рабочие могут работать самостоятельно, Gearman - лучший способ сделать это. Но если вы пытаетесь отправить данные из множества источников в меньшее количество потребителей данных, RabbitMQ является лучшим решением.

История RabbitMQ, как того, что позволяло Twitter принимать бурные партии сообщений и передавать их в разрушительные старые SMS-шлюзы, которые могли держать открыто только одно соединение, были ограничены по скорости и не имели попыток, является иллюстрацией типа проблем, которые RabbitMQ хорошо решает.

Есть еще более простой способ сделать это, если вы переопределяете touchesНачало: вам нужно сделать оператор if, чтобы решить, находится ли он в пределах близости галочек, если это не вызов [super touchesНачало: касания withEvent: event] и будет действовать так, как если бы он был выбран.

в C, это почти Алгоритм Шлемиэля Живописца (не совсем O (n!), но более 0 (n2)).

Но будет превосходить «лучшие» алгоритмы для последовательностей разумного размера, потому что O так мал. Это также позволяет легко определить местоположение первого неповторяющегося ряда.

char FirstNonRepeatedChar(char * psz)
{
   for (int ii = 0; psz[ii] != 0; ++ii)
   {
      for (int jj = ii+1; ; ++jj)
      {
         // if we hit the end of string, then we found a non-repeat character.
         //
         if (psz[jj] == 0)
            return psz[ii]; // this character doesn't repeat

         // if we found a repeat character, we can stop looking.
         //
         if (psz[ii] == psz[jj])
            break; 
      }
   }

   return 0; // there were no non-repeating characters.
}

edit: этот код предполагает, что вы не имеете в виду последовательных повторяющихся символов.

Это должно быть по крайней мере O(n), потому что вы не знаете, будет ли символ повторяться, пока не прочитаете все символы.

Поэтому вы можете перебирать символы и добавлять каждый символ в список, когда вы видите его в первый раз, и отдельно вести подсчет того, сколько раз вы его видели (на самом деле единственные значения, которые имеют значение для подсчета, это "0", "1" или "более 1").

Когда вы дойдете до конца строки, вам нужно будет просто найти первый символ в списке, у которого счетчик равен единице.

Пример кода на Python:

def first_non_repeated_character(s):
    counts = defaultdict(int)
    l = []
    for c in s:
        counts[c] += 1
        if counts[c] == 1:
            l.append(c)

    for c in l:
        if counts[c] == 1:
            return c

    return None

Это выполняется за O(n).

Counter требует Python2.7 или Python3.1

>>> from collections import Counter
>>> def first_non_repeated_character(s):
...     counts = Counter(s)
...     for c in s:
...         if counts[c]==1:
...             return c
...     return None
... 
>>> first_non_repeated_character("aaabbbcddd")
'c'
>>> first_non_repeated_character("aaaebbbcddd")
'e'

Вот еще один забавный способ сделать это. Счетчик требует Python2.7 или Python3.1

>>> from collections import Counter
>>> def first_non_repeated_character(s):
...     return min((k for k,v in Counter(s).items() if v<2), key=s.index)
...
>>> first_non_repeated_character("aaabbbcddd")
'c'
>>> first_non_repeated_character("aaaebbbcddd")
'e'

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