LINUX.ORG.RU

bash Работа со строками и столбцами.

 , ,


0

2

Здравствуйте! Помогите, пожалуйста, нубу) Есть следующая задча. Столбец:

  • aaa
  • bbb
  • ccc

Необходимо средствами баш сделать следующее:

  • aaa bbb
  • aaa ccc
  • bbb aaa
  • bbb ccc
  • ccc aaa
  • ccc bbb

Заранее большое спасибо!



#!/bin/bash

declare -A result

while read inp; do
    for P in "${indata[@]}"; do
        result["$inp $P"]=1
        result["$P $inp"]=1
    done
    indata+=("$inp")
done

for key in "${!result[@]}"; do 
    echo "$key"
done
$ printf "aaa\nbbb\nccc\n" | ./pairs.sh 
ccc aaa
aaa ccc
bbb aaa
bbb ccc
aaa bbb
ccc bbb

$ printf "aaa\nbbb\nccc\nddd\n" | ./pairs.sh 
ddd ccc
ccc aaa
aaa ccc
bbb ddd
bbb aaa
ddd aaa
bbb ccc
aaa bbb
aaa ddd
ddd bbb
ccc ddd
ccc bbb
futurama ★★★★★
()
Последнее исправление: futurama (всего исправлений: 1)
Ответ на: комментарий от futurama

Работает, но довольно неэффективно. Вы сортируете/хешируете O(N^2) элементов когда можно обойтись O(N) в худшем случае. Чем плохо бегать вложенным for-лупчиком по одному входному массиву и печатать «на лету»? Дубликаты (если нужно) лучше отфильтровать на входе (например через sort | uniq). Правда тогда порядок съедет - но он у Вас и так не сохраняется.

ПыСы. А если выборки по 3 печатать у Вас вообще куб вылезает, ну итд.

bugfixer ★★★★★
()
Ответ на: комментарий от Balamoot

По тексту вопроса понятно, что это задачка из лабы, которую студент хочет нахаляву решить с помощью лора. Обычно в лабах ограничивают список утилит, которыми можно пользоваться. Так что твоя тысяча здесь бесполезна. В задании сказано только про баш.

ox55ff ★★★★★
()
Ответ на: комментарий от futurama

можно не хешировать, а сразу выкидывать в stdout память сэкономим здесь

Всё правильно.

потом на uniq потеряем

Нет - потеряем «до» и O(N) если делать алгоритмически правильно.

кроме памяти, все-равно будет производительность О(n^2)

Это правда. Time cost остаётся O(N^2), space cost сильно уменьшается.

bugfixer ★★★★★
()
Ответ на: комментарий от bugfixer

С точки зрения оценки алгоритма, расход памяти все-равно N^2, не важно куда мы результат скинули в хеш или в stdout

Или я путаю размер результата и промежуточный расход памяти для достижения результа?

futurama ★★★★★
()
Последнее исправление: futurama (всего исправлений: 1)
Ответ на: комментарий от futurama

С точки зрения оценки алгоритма, расход памяти все-равно N^2, не важно куда мы результат скинули в хеш или в stdout

Не не не. По памяти там O(N) если всё сделать правильно. «Бегать» придётся O(N^x) по любому (в зависимости от того какой длины выборки делаем).

ПыСы. С тем что размер выхлопа растёт как N^x - я не спорю. Но это не то что включают в space cost.

bugfixer ★★★★★
()
Последнее исправление: bugfixer (всего исправлений: 1)
Ответ на: комментарий от bugfixer

Тогда мой хеш – это просто хранилище результата, а память для работы алгоритма N (для хранения входных данных)

Так какие претензии к эффективности?

futurama ★★★★★
()
Последнее исправление: futurama (всего исправлений: 1)
Ответ на: комментарий от futurama

Так какие претензии к эффективности?

Алгоритмически - исключительно space cost. Неужели Вы не видите насколько оно плохо, на пустом месте (спешу заметить)? Ладно бы упрощало чего…

bugfixer ★★★★★
()
Ответ на: комментарий от bugfixer

Ты меня начинаешь бесить. !!! Хеш не является частью алгоритма !!!, можно вместо записи в хеш просто делать echo

Для работы алгоритма нужен только список входных данных размером N

П.С. Продолжения не будет.

futurama ★★★★★
()
Ответ на: комментарий от futurama

это хранилище результата (тебе результат не нужен что-ли?)

Нужен. Но размер результата к потреблению памяти «в процессе» мало имеет отношения. Смотрите на это как на «отдал, и забыл».

bugfixer ★★★★★
()
Ответ на: комментарий от futurama

Ты меня начинаешь бесить. !!! Хеш не является частью алгоритма !!!

Ну, извиняйте :) Если бы мы следовали Вашим заповедям - мы бы разорились на закупках RAM дабы дооснастить машинки во всех наших DC, я не шучу сейчас…

bugfixer ★★★★★
()
Ответ на: комментарий от futurama

Ты программист?

Да, программист.

Если да, то у меня для тебя плохие новости, ты профнепригоден. я не шучу сейчас…

В оценках своих квалификаций позволю себе ориентироваться исключительно на мнение своего начальства.

bugfixer ★★★★★
()