Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / работа со списками / 24 сообщений из 24, страница 1 из 1
28.10.2013, 16:59
    #38443867
sergq
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
Здравствуйте.

Имеется два списка упорядоченных элементов.

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


Подскажите куда копать


Спасибо
...
Рейтинг: 0 / 0
28.10.2013, 17:13
    #38443896
sergq
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
все вроде хорошо, но вот этого

И добавить все записи из первого, которых нет во втором.

в один проход не получается
...
Рейтинг: 0 / 0
28.10.2013, 18:00
    #38443989
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
Долго ржал... ты вообще думаешь, что пишешь?

авторполучить третий список, в который включит в себя все элементы из второго списка, которых есть в первом
То есть элементы, которые есть И в первом списке, И во втором.

авторИсключить из результирующего списка все элементы из второго списка, которых которых нет в первом.
Тебе не очевидно, что таковых в итоговом списке нет?

автордобавить все записи из первого, которых нет во втором
Были все записи из первого, которые есть во втором. добавили все из первого, которых нет во втором. Что получили? первый список, из которого выброшены дублирующиеся записи.
...
Рейтинг: 0 / 0
28.10.2013, 18:56
    #38444055
sergq
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
Akina,

Ага. Видимо напутал по конец дня.

Вот так должно быть.

1. Все элементы которые есть И в первом списке И во втором.
2. Включить в результирующий все элементы первого списка, которых нет во втором.
3. НЕ ВКЛЮЧАТЬ в результрирующий список элементы второго списка если их нет в первом.
...
Рейтинг: 0 / 0
28.10.2013, 19:00
    #38444062
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
sergqПодскажите куда копать
Копать нужно в сторону цикла while который обходит все элементы первого
списка.
...
Рейтинг: 0 / 0
28.10.2013, 19:02
    #38444065
k0rvin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
sergqAkina,

Ага. Видимо напутал по конец дня.

Вот так должно быть.

1. Все элементы которые есть И в первом списке И во втором.
2. Включить в результирующий все элементы первого списка, которых нет во втором.
3. НЕ ВКЛЮЧАТЬ в результрирующий список элементы второго списка если их нет в первом.
Та же самая пурга, получаем просто первый список.
...
Рейтинг: 0 / 0
28.10.2013, 19:06
    #38444069
ДохтаР
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
sergqAkina,

Ага. Видимо напутал по конец дня.

Вот так должно быть.

1. Все элементы которые есть И в первом списке И во втором.
2. Включить в результирующий все элементы первого списка, которых нет во втором.
3. НЕ ВКЛЮЧАТЬ в результрирующий список элементы второго списка если их нет в первом.

Нужно запрогать LEFT OUTER JOIN .
...
Рейтинг: 0 / 0
28.10.2013, 19:30
    #38444088
sergq
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
mayton,

С первыми двумя пунктами вроде разобрался.

А вот с третьим.
Можно все это сделать за один проход по списку?
...
Рейтинг: 0 / 0
28.10.2013, 19:40
    #38444095
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
sergqmayton,

С первыми двумя пунктами вроде разобрался.

А вот с третьим.
Можно все это сделать за один проход по списку?
Нет. Можно один из списков загнать в TreeSet или HashSet и работать как будто в
"один проход". Но всё равно фул-скан обоих списков по заданию придётся сделать
хотя-бы 1 раз.
...
Рейтинг: 0 / 0
28.10.2013, 22:32
    #38444201
sergq
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
mayton,

Посудите, но не строго )

первые два пункта
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
  while ((not sourceQuery.Eof) or (not destQuery.Eof)) do
  begin
        if sourceQuery.Eof then
        Break;
        if destquery.Eof then
        begin
        Break;
        end;
      while sourceQuery.FieldByName('c').AsInteger < self.destQuery.FieldByName('c').AsInteger do
      begin
         //!!!  включаем в результат и получаем следующее значение
        if sourceQuery.Eof then Break;
        if destquery.Eof then Break;

         sourceQuery.Next;
      end;

      if sourceQuery.FieldByName('c').AsInteger = destQuery.FieldByName('c').AsInteger then
      begin
        //!!!  включаем в результат и получаем следующее значение
        sourceQuery.Next;
      end;

      while ((sourceQuery.FieldByName('c').AsInteger > destQuery.FieldByName('c').AsInteger))
      do
      begin
        destQuery.Next;
        if sourceQuery.Eof then Break;
        if destquery.Eof then  Break;
      end;
  end;

  // добиваем остаток списка 
  if not sourcequery.eof and destquery.eof then
  begin
      //!!!  включаем в результат и получаем следующее значение
      while not sourcequery.eof do
        sourcequery.next;
  end;



с третьим пунктом 3. НЕ ВКЛЮЧАТЬ в результирующий список элементы второго списка если их нет в первом.
что-то перемудрил, но работает


Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
  sourceQuery.First;
  destQuery.First;
  while not sourceQuery.Eof or destQuery.Eof do
  begin
      if sourceQuery.FieldByName('c').AsInteger = destQuery.FieldByName('c').AsInteger then
      begin
        sourceQuery.Next;
        destQuery.Next;
      end;
      while ((sourceQuery.FieldByName('c').AsInteger > destQuery.FieldByName('c').AsInteger))
      do
      begin
        if sourceQuery.Eof then Break;
        if destquery.Eof then Break;
        end;
        // тут исключаем из результата по ИД destquery и получаем следующее значение
        destQuery.Next;
      end;

        if sourceQuery.Eof then Break;
        if destquery.Eof then Break;
        end;

      while sourceQuery.FieldByName('c').AsInteger < self.destQuery.FieldByName('c').AsInteger do
      begin
           // тут исключаем из результата по ИД destquery и получаем следующее значение
           // Но в результате получаются задвоенные ИД
           sourceQuery.Next;
           if sourceQuery.Eof then Break;
           if destquery.Eof then Break;
        end;
      end;
  end;
  // добиваем список
  while not destquery.eof then
  begin
     // тут исключаем из результата по ИД destquery и получаем следующее значение
     destquery.next;
  end;
...
Рейтинг: 0 / 0
29.10.2013, 01:00
    #38444303
ДохтаР
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
sergq,


Обратите внимание :
sergqдва списка упорядоченных элементов

проходя по первому списку и по второму паралельно в одном теле цикла , сравнивая эелементы между собой и на больше меньше (списки упорядочены)
за один проход( цикл) можно отобрать все, что вам нужно.
...
Рейтинг: 0 / 0
29.10.2013, 01:03
    #38444304
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
А ведь док. прав. Это будет по аналогии с Merge Sort.
...
Рейтинг: 0 / 0
29.10.2013, 08:44
    #38444415
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
ДохтаРОбратите внимание :
sergqдва списка упорядоченных элементов

Без дополнительного указания, что считается упорядоченностью (причём для каждого списка отдельно! где гарантия, что одно и то же?), этими сведениями можно смело пренебречь.
...
Рейтинг: 0 / 0
29.10.2013, 09:09
    #38444433
sergq
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
Вот такой вопрос возник.

При проходе по спискам сравниваем ключ. И на основании этого сравнения делаем выводы.
Хорошо , что если ключ один в каждом списке.

А вот как быть как сравнивать, если в каждом списке в строке да и более ключа? Т.е по аналогии с базами данный PK состоит не из одного поля, а из двух или трех
...
Рейтинг: 0 / 0
29.10.2013, 09:44
    #38444469
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
А это уже твоя забота. Не знаешь - тряси преподавателя.
...
Рейтинг: 0 / 0
29.10.2013, 11:50
    #38444683
ДохтаР
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
AkinaДохтаРОбратите внимание :
пропущено...


Без дополнительного указания, что считается упорядоченностью (причём для каждого списка отдельно! где гарантия, что одно и то же?), этими сведениями можно смело пренебречь.

Есть два варианта
1. Задачу поставил лид или архитектор.
2. Задачу дал преподаватель.

Во всех перечисленных случаях , когда исполнитель проигнорил слово " упорядоченных " он зафейлится.
В первом случае как велосипедостоитель перед руководсвом и коллегами, во втором получит двойку за невнимательность.
...
Рейтинг: 0 / 0
29.10.2013, 12:03
    #38444710
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
ДохтаР , критерий упорядочивания может оказаться недостаточным для сравнения. Посему упорядоченность может оказаться недостаточной для поиска (не)вхождений эмуляцией сортировки слиянием.
...
Рейтинг: 0 / 0
29.10.2013, 12:26
    #38444745
ДохтаР
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
Akina ДохтаР , критерий упорядочивания может оказаться недостаточным для сравнения. Посему упорядоченность может оказаться недостаточной для поиска (не)вхождений эмуляцией сортировки слиянием.


В общем случае , да.
В случае формализованной постановки задачи - НЕТ.
Если упорядоченность не помагает решать задачу, в условии о ней не говорят.
просто упускают , оставляя на откуп реализующему.

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

Формальная логика постановщика должна соотвествать формальной логике реализующего,
приблизительно так.
...
Рейтинг: 0 / 0
29.10.2013, 12:28
    #38444753
ДохтаР
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
Akina ДохтаР , критерий упорядочивания может оказаться недостаточным для сравнения. Посему упорядоченность может оказаться недостаточной для поиска (не)вхождений эмуляцией сортировки слиянием.


Нельзя упорядочить не сравнивая.
...
Рейтинг: 0 / 0
29.10.2013, 12:50
    #38444807
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
Вот скажем ставят тебе задачу: есть два почтовых ящика, упорядоченных по дате-времени получения писем, отбери письма, имеющиеся в обоих ящиках...

Набор упорядочен? да, вполне себе тянет на связный список. Можно ли эту упорядоченность использовать для решения поставленной задачи? нельзя.

ДохтаРЕсли упорядоченность не помагает решать задачу, в условии о ней не говорят.
просто упускают , оставляя на откуп реализующему.

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

Формальная логика постановщика должна соотвествать формальной логике реализующего,
приблизительно так.
Вот есть категория людей, у которых от рождения к ногам привязаны грабли...

Всё, что не указано явно, может быть как угодно.
Для этого и существует этап детализации и уточнения задачи. Для этого и разрабатывают ТЗ стоимостью в полпроекта. На этом и горят тупые студенты.
...
Рейтинг: 0 / 0
29.10.2013, 13:21
    #38444884
ДохтаР
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
AkinaВот скажем ставят тебе задачу: есть два почтовых ящика, упорядоченных по дате-времени получения писем, отбери письма, имеющиеся в обоих ящиках...

Набор упорядочен? да, вполне себе тянет на связный список. Можно ли эту упорядоченность использовать для решения поставленной задачи? нельзя.


Мне таких глупых задач не ставят, и слава Богу



AkinaВот есть категория людей, у которых от рождения к ногам привязаны грабли...


Задача решается через left outer join за 3 минуты, не зависимо от того что как посортировано.
нефик изобретать алгоритмические велосипеды за счет работодателя.

AkinaВсё, что не указано явно, может быть как угодно.
Для этого и существует этап детализации и уточнения задачи. Для этого и разрабатывают ТЗ стоимостью в полпроекта. На этом и горят тупые студенты.


Исходя из упрощенной постановки в топике подразумевается, что задача школькно-учебная и упорядоченность правильная.
...
Рейтинг: 0 / 0
29.10.2013, 13:24
    #38444893
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
ДохтаРИсходя из упрощенной постановки в топике подразумевается, что задача школькно-учебная и упорядоченность правильная.
Исходя из опыта чтения форумных тем с учебными задачами я обычно делаю строго противоположный вывод. Но, опять же исходя из опыта - бОльшую часть преподавателей устраивает любое решение, отвечающее любому из возможных пониманий условия.
...
Рейтинг: 0 / 0
29.10.2013, 13:31
    #38444917
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
Это обычная лаба по спискам.
...
Рейтинг: 0 / 0
29.10.2013, 13:55
    #38444978
goldmi45
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
работа со списками
AkinaВот скажем ставят тебе задачу: есть два почтовых ящика, упорядоченных по дате-времени получения писем, отбери письма, имеющиеся в обоих ящиках...

Набор упорядочен? да, вполне себе тянет на связный список. Можно ли эту упорядоченность использовать для решения поставленной задачи? нельзя.

Два списка упорядочены, но не связаны.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / работа со списками / 24 сообщений из 24, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]