newbee wrote:Двуручник wrote:Если лист большой можно и по-замысловатее, чтоб побыстрее работало...
aList.Sort();
Это уже как минимум ln(n)*n, а предлагаемые до этого алгоритмы тупого перебора дают n
На самом деле все равно будет быстрее чем "тупого перебора", за исключкнием Sam Adams который в общем далеко не "тупого перебора".
Вот объясниите мне, почему нужен обязательно замысловатее?
В реальной жизни мв играемся с факторами K1* производительности(память/CPU)+K2*гибкость+K3*читабельность(время на понимание что код делает=> время нужное чтобы надти проблему или его модифицировать). В большей части случаев K3>>K1, но на интервью ожидают увидеть
Code: Select all
int j = 0;
for (int i = 0; i < list.Length; i++)
{
if ((string)list[i]).StartsWith(prefix))
{
list[j++] = list[i];
}
}
if (list.Length != j)
{
list.Remove(j, list.Length - j);
}
Сколько времени нужно чтобы понять, что этот алгоритм делает? Мне, на первый взгляд, кажется что он забивает строками StartsWith(prefix) начало массива, а потом удаляет из середины кусок еще незабитых строк.
Двуручник особенно если снабдит комментами
Code: Select all
aList.Sort();
int start = aList.Count;
for(int i=0; i<aList.Count; i++) {
if(aList[i].ToString().StartWith("A")) { start = i; break; }//первый элемент "A.."
}
int end = -1;
for(int i=aList.Count; i>=0; i--) {
if(aList[i].ToString().StartWith("A")) { end = i; break; }//последний элемент "A.."
}
aList.RemoveRange(start,end-start);
гораздо понятней, хотя тоже не идиал.. не говоря о том, что порядок элементов в исходном массиве мог иметь значение.
Сравните с
Code: Select all
String bla = "A";
ArrayList noBlaInList = new ArrayList();
for( int i=0; i< blaInList.size(); i++ ){
// add only noBla elements
if(!((String) listWithBla.get(i)).startsWith(bla))
noBlaInList.add(listWithBla.get(i));
}
Code: Select all
//ecли нужна гибкость – не ограничиваем тип входной коллекции ArrayList
// Iterator нам кое-что будет стоить, но непринципиально
String bla = "A";
Iterator it = listWithBla.iterator();
ArrayList noBlaInList = new ArrayList();
/*creates ArrayList without starts With bla elements */
while(it.hasNext()){
String s = (String)it.next();
if(!s.startsWith(bla))noBlaInList.add(s);
}
Code: Select all
//ecли нужно очистить исходный list убираем "!" и “no”
String bla = "A";
Iterator it = list.iterator();
ArrayList blaInList = new ArrayList();
while(it.hasNext()){
String s = (String)it.next();
if(s.startsWith(bla))blaInList.add(s);
}
list.removeAll(blaInList);
или
IMO за исключкнием
List<string> a = ...
a.RemoveAll(delegate(string s) { return s.StartsWith("A"); });
самое читаемое решение.
Я не работал с FW2 (да и вообще с .NET только раз довелось поработать), но интуитивно код понятен. Вот интересно его по произволитеотности сравнить с моим, особенно по памяти.
Может мне кто объяснить почему на интервью отдают предпочтение не простым и практичным решениям, а позамысловатее.. причем обе стороны.
Помнится кто-то MS задачку подкинул .. что-то типа посчитать количество бензоколонок в US.. как потом выяснилось нужно порассуждать о потреблении бензина, etc. в результате ответ будет +/- порядки.. зачем? Бензоколоноки – бизнес который обязательно регистрировать => можно найдти совершенно точную (ну может не совсем свежую) информацию. Т.е. ожидается не решение проблемы, а упражнения "смотри какой я умный"
