РЕДАКТИРОВАНИЕ:
О, я понял сейчас, под "кратным" вы подразумевали "больше двух", а значения не имеют целых чиселидентификаторы, строки ввода do.Хорошо, давайте начнем сначала.
Вам действительно нужно хранить входы?Если какой-либо вход false, выход false, поэтому просто выводите true, если у вас есть хотя бы один (или два, если вы предпочитаете) входы, которые true, и до тех пор, пока вы не получите вход, которыйfalse.
О, но вы сказали, что «два сигнала, поступающие на один и тот же вход, не считаются как два».Чтобы обеспечить это, у вас есть для отслеживания (но не обязательно сохранения) входных данных.Это то, к чему это действительно сводится.
Итак, настоящий вопрос: Как эффективно хранить (и извлекать) разреженный массив целых чисел в C #?
Словарь (хеш-таблица), безусловно, является очевидным выбором, когда вы говорите о разреженных массивах.Но в этом случае вам нужно только логическое значение для каждой записи, и Dictionary<int, bool> действительно несколько расточительно.
Каков максимальный диапазон идентификаторов строки ввода?Это [int.MinValue, int.MaxValue] или что-то в более управляемом диапазоне?Если максимальный диапазон идентификаторов относительно мал, возможно, вы захотите посмотреть System.Collections.BitArray или System.Collections.Specialized.BitVector32.
Если вы используете одну из этих битовых коллекций, у вас есть два варианта:
- Используйте два BitArrays / BitVector32s: один для хранения входных значений, а другой для хранения того, поступил ли сигнал на эту линию.
- Используйте только один BitArray / BitVector32.Используйте его для хранения того, поступил ли сигнал на данную строку или нет, и сохраните отдельное значение
bool, которое будет добавляться к каждому новому входу.Эта опция не позволяет переустанавливать вход false в строке на вход true в той же строке.
Предполагая 32 или менее строк ввода, эффективная реализация опции BitVector321 выше будет выглядеть примерно так:
class AndGate{
BitVector32 activeLines;
BitVector32 inputValues;
public void Reset(){
activeLines[-1] = inputValues[-1] = false;
}
public void Input(int line, bool value){
if(line < 0 || line > 31)
throw new ArgumentOutOfRangeException("line");
activeLines[1 << line] = true;
inputValues[1 << line] = value;
}
public bool GetOutput(bool reset){
bool rtn = activeLines.Data == inputValues.Data;
if(reset)
Reset();
return rtn;
}
}
Если вам нужно более 32 строк, эквивалентная реализация с BitArray будет аналогичной, за исключением того, что GetOutput будет более сложным и менее эффективным.Возможно, вам лучше использовать собственный BitArray эквивалент, используя BitVector32 s (или просто int / uint s).
EDIT2:
Учитывая возражения ОП, я могу только предположить, что ожидаемые идентификаторы строк находятся в [int.MinValue, int.MaxValue], и что строки могут быть переключены с false на true.Если это действительно так, то плотная реализация, такая как я описал выше, нецелесообразна.
Так что мы вернулись к Dictionary<,>.Однако есть еще пара оптимизаций, которые мы можем сделать за Dictionary<int, bool>.
Один из них - использовать SortedList<,>.Если может быть дано очень большое количество входов, SortedList<,> будет использовать значительно меньше памяти, чем Dictionary<,>.
Например, в Dictionary<int, bool> каждая запись будетиспользовать не менее 17 байт памяти.SortedList<int, bool> будет использовать только 5.
Самый большой недостаток 1 заключается в том, что добавление новой записи в SortedList<,> обычно значительно медленнее, чем добавление записи в Dictionary<,>, посколькудругие записи, чьи ключи сравниваются больше, чем добавленная запись, должны быть сдвинуты вниз, чтобы освободить место для новой записи.Я бы порекомендовал профилирование с ожидаемыми входными данными для сравнения использования памяти и производительности процессора между SortedList<,> и Dictionary<,>.
Другая оптимизация заключается в объединении подхода BitVector32, который я упоминал вышес Dictionary<,> / SortedList<,>.Это потенциально 2 не позволяет большому количеству потраченного впустую пространства хранить логическое значение в 8 битах, а также хранить много ключей и (если применимо) служебные данные хеш-таблицы.
Пример реализации, допускающий обе эти концепции, следующий:
class AndGate{
struct AndEntry{
BitVector32 activeLines;
BitVector32 inputValues;
public bool Output{get{return activeLines.Data == inputValues.Data;}}
public void Input(int line, bool value){
activeLines[1 << line] = true;
inputValues[1 << line] = value;
}
}
IDictionary<int, AndEntry> entries;
public AndGate(bool useSortedList){
if(useSortedList)
entries = new SortedList<int, AndEntry>();
else entries = new Dictionary<int, AndEntry>();
}
public void Reset(){entries.Clear();}
public bool Input(int line, bool value){
AndEntry entry;
entries.TryGetValue(line / 32, out entry);
/* no need to handle the not found case, since AndEntry is a struct */
entry.Input(line & 31, value);
entries[line / 32] = entry;
}
public bool GetOutput(bool reset){
bool rtn = true;
foreach(AndEntry value in entries.Values)
if(!value.Output){
rtn = false;
break;
}
if(reset)
Reset();
return rtn;
}
}
Имейте в виду, что единственное преимущество этих оптимизаций - это использование меньшего количества памяти. Это имеет значение, только если вы ожидаете много входов. Что именно означает «многие», трудно привязать, но назовите это 20 байтов для каждой записи (для учета накладных расходов) для простой реализации Dictionary<int, bool>. Итак, разделите количество памяти, которое вы хотите использовать, на 20. Вот что такое «много». Но остерегайтесь компромисса между процессором и памятью.
1 Прежде чем кто-то наивно утверждает, что реальным недостатком отсортированного списка по хеш-таблице (то есть, как реализовано Dictionary<,>) является то, что поиск в отсортированном списке медленнее по сравнению с хеш-таблицей, не надо , «Но поиск - это O (log N) в отсортированном списке, и только O (1) в хэш-таблице», - скажут они. Whoop-де-Freakin-до. С одной стороны, хеш-таблицы потенциально уменьшаются до O (N), тогда как отсортированный список всегда равен O (log N). Для двух, даже если у вас есть миллиард предметов, 30 целочисленных сравнений (как это было бы в этом случае) просто не стоило бы так дорого. Что касается издержек хеш-таблицы, многие удивляются, узнав, как часто отсортированные списки превосходят хеш-таблицы при поиске.
2 Опять же, это зависит от ваших входов. Если lineID & ~31 не часто перекрывается (поэтому большинство AndEntry объектов в конечном итоге хранят только одну строку), тогда это решение будет использовать больше памяти, а не меньше. Если вместо этого какой-то другой набор из 27 битов в lineID имеет тенденцию перекрываться, то другие маски в Input() будут более эффективными.