Маленькая задачка- Разработка программ

Гость

0 - 25.09.2014 - 16:05

Предлагаю ради фана попробовать реализовать лучшим способом.

Задача: Вывести на экран числа, которые встречаются минимум два раза в разных строках файла.

Пример содержимого файла:
1 2 3 2
4 5 6 4
7 6 5 0

Предполагаемый результат: 5, 6

Мой вариант на Scala:

import scala.annotation.tailrec
import scala.io.Source

object Test extends App **
@tailrec def getListSet(iterator: Iterator[String], res:List[String]): List[String] =
if (!iterator.hasNext) res
else getListSet(iterator, iterator.next().split("\\s+").toSet.toList ::: res)

val filename = "c:\\digits.txt"
val result = getListSet(Source.fromFile(filename).getLines(), Nil)
.groupBy(k => k).filter(_._2.length > 1).keys
print(result.mkString(","))
**

Гость

1 - 26.09.2014 - 08:09

Мой вариант на ObjectPascal с личными библиотеками.

program Fun ;

**$ifdef fpc****$mode objfpc****$h+****$endif**

uses TAVIntList, TAVStringFile ;

var IL:TIntList ;
ILK:TIntKeyList ;
i:Integer ;
begin

ILK:=TIntKeyList.Create() ;

with TStringFile.Create('C:\File.txt') do begin
while not EOF() do begin
IL:=TIntList.CreateFromSepList(ReadLine(),#32,[ilcRemoveRepeat]) ;
for i:=0 to IL.Count-1 do ILK.Inc(IL[i]) ;
IL.Free ;
end ;
Free ;
end ;

for i:=0 to ILK.Count-1 do
if ILK.Values[i]>=2 then Writeln(ILK.Key[i]) ;

ILK.Free ;
end.

Без библиотек, конечно, будет раза в 4 длиннее.

Гость

2 - 26.09.2014 - 10:18

Полагаю Python с его срезами и tuples будет самым немногословным, а если еще и с применением его стандартной библиотеки re - тем паче.

Алгоритм вижу такой (писать лень):

1) построчно считать файл и записать в двумерный XY-массив

2) каждую "строку" массива отсортировать по знакоместу/возрастанию (индексу), получится типа:
[plain]
1 2 3
4 5 6
5 6 7 0
[/plain]

3) просуммировать столбцы. >=2 - вывести.

Гость

3 - 26.09.2014 - 10:20

Код:

1 2 3 
      4 5 6 
        5 6 7 0

Гость

4 - 26.09.2014 - 11:07

C#, .NetFramework 4.0, WinFormsApplication

using System;
using System.IO;
using System.Windows.Forms;

namespace WindowsFormsApplication1
**
public partial class Form1 : Form
**
public Form1()
**
InitializeComponent();
**

private void button1_Click(object sender, EventArgs e)
**
string[] arraySTRING = File.ReadAllLines("test.txt");

for (int i = 0; i < arraySTRING.Length; i++)
**
string[] separators = **" "**;
string[] temp = arraySTRING[i].Split(separators, StringSplitOptions.RemoveEmptyEntries);

for (int j = 0; j < temp.Length; j++)
**
for (int k = 0; k < arraySTRING.Length; k++)
**
if (k != i)
**
if (arraySTRING[k].Contains(temp[j]))
**
if (listBox1.Items.Contains(temp[j]) == false)
listBox1.Items.Add(temp[j]);
break;
**
**
**
**
**
**
**
**

Гость

5 - 26.09.2014 - 11:18

Комментарии обработчика кнопки:

// считываем в массив текстовый файл
string[] arraySTRING = File.ReadAllLines("test.txt");
// получаем массив из трёх элементов вида
// ** 1 2 3 2 , 4 5 6 4 , 7 6 5 0 **

// начинаем цикл по каждому элементу массива arraySTRING
for (int i = 0; i < arraySTRING.Length; i++)
**
// знак разделитель, функция Split воспринимает только массивы разделителей
string[] separators = **" "**;
// получаем массив temp элементов из одного элемента массива arraySTRING
string[] temp = arraySTRING[i].Split(separators, StringSplitOptions.RemoveEmptyEntries);

// начинаем вложенный цикл по каждому элементу массива temp
for (int j = 0; j < temp.Length; j++)
**
// начинаем ещё один вложенный цикл по начальному массиву arraySTRING
for (int k = 0; k < arraySTRING.Length; k++)
// если это не исходный элемент массива arraySTRING
if (k != i)
// если элемент массива arraySTRING содержит элемент массива temp
if (arraySTRING[k].Contains(temp[j]))
**
// проверка на повторный результат
if (listBox1.Items.Contains(temp[j]) == false)
// добавляем результат в список
listBox1.Items.Add(temp[j]);
// обрываем цикл
break;
**
**
**

Гость

6 - 26.09.2014 - 23:02

2-economist > Идея интересная, но есть несколько вопросов:
1. Что делать с повторами?
2. Чтобы выбрать место надо составить список всех чисел в файле?

С остальными все более менее понятно. Еще бы оценки алгоритмам высчитать.

Гость

7 - 27.09.2014 - 09:58

По каким параметрам алгоритм "самый лучший"? Самый короткий? Быстрый? Жрет памяти меньше всего? Ну и набор тестов надо бы нормальный - матрица 3х3 это не серьезно.

Гость

8 - 27.09.2014 - 11:35

Предлагаю матрицу 10000x10000 с значениями от 0 до 100000.
Замерить время выполнения алгоритмов.

Гость

9 - 29.09.2014 - 10:39

7-JustPass > O-нотация?
Если я не забыл как оно считается, то для решения в 0 получается для входного NxM: O(N^4*M^6).
Что есть до хрена =)

Гость

10 - 29.09.2014 - 23:49

O() было бы конечно хорошо, но боюсь упремся в детали реализации языков. Несколько матриц (думаю хватит 1000х1000) и замерим время на примерно одинаковых машинах. Есть тесты? Можно конечно написать генератор, только кто его проверять будет? =)

Гость

11 - 30.09.2014 - 08:07

40KHYTbIU - повторы надо убирать, конечно. А знакоместо выбирать не нужно, это же индекс (0-9), Прямо по нему и писать в массив.

Все эти алгоритмические задачи "для удовольствия" несут немного пользы. Вот пример маленькой программы, которая шлет SMS сообщения через модем или моб. телефон, взяв данные из таблицы 1С - на Python.

Код:

# -*- coding: utf-8 -*-
import os        # все 8 тысяч библиотек 
import re        # языка Python -
import SMSSender # бесплатные!

a = SMSSender(3) #в () - номер COM-порта

# Код задействует кортежи, цикл и срезы строк.
# прочтем текстовый файл с разделителями табуляция: 
# 79181234567 Оплатите задолженность 30000 руб.	
# Это файл может быть получен из MS Excel или OpenOffice/LibreOffice Calc (через 1С итп)

reportFile=open('C:/sms_texts.txt', 'r') 

for line in reportFile:
    sms=re.split("\t", line)
    tel=sms[0],
    smsuni=sms[1].decode('cp1251') # Декодировали 1С/MSO итп) в utf-8
    a.sendMessage(tel, smsuni)
    time.sleep(20)

Гость

12 - 30.09.2014 - 09:30

Цитата:

Сообщение от JustPass

Несколько матриц (думаю хватит 1000х1000)

От 0 и до скольки? Я думаю для чистоты эксперимента должен быть максимум 10 000 хотя бы. Чтобы в выборки строк не попадались часто одни и те же значения.

Цитата:

Сообщение от JustPass

Можно конечно написать генератор, только кто его проверять будет

Я написал для себя генератор. Рандомом (в зависимости от текущей даты) генерит матрицу заданных размеров. Только файл txt не хилый получился, для матрицы 10 000х10 000 весил около 200 МБ.

Гость

13 - 01.10.2014 - 21:48

Вот шота мне думается, что это на Lisp'e нада налобать.

Гость

14 - 01.10.2014 - 22:58

13-Zobkor >welcome!
11-economist >к чему это все, еще и с рекламой?
10-JustPass >о каких деталях речь? Алгоритм можно оценить вполне конкретно, реализация дело поправимое.

Гость

15 - 02.10.2014 - 15:06

40KHYTbIU - просто пример полезной программы. А "реклама" бесплатного языка - это вовсе не реклама, а популяризация. Тасазать свет знаний.

Гость

16 - 03.10.2014 - 21:13

на бейсике, ля:)) if 1.1=1 then a+1, if a=> 2 print" Две единицы" бггг

Гость

17 - 30.10.2014 - 17:04

С#, .NET 4.0, LINQ

string buffer = File.ReadAllText("c:\\1\\1.txt");
List<char> chars = buffer.ToList<char>();
chars=chars.FindAll(c1 => chars.FindAll(c2 => c2 == c1).Count >= 2).Distinct().ToList();
foreach (char c in chars) Console.WriteLine(c);

Гость

18 - 30.10.2014 - 17:28

17-LostDaemon > а можно подробнее на словах?
А то мне кажется что если на входе:
2 2
1 1
У вас вернет 2 и 1.

Гость

19 - 31.10.2014 - 10:34

Так и есть, я пропустил "мимо ушей" ключевое слово "В разных".
Вот корректировочка:

string buffer = File.ReadAllText("c:\\1\\1.txt");
List<char> chars = buffer.ToList<char>();
chars = chars.FindAll(c1 => chars.FindAll(c2 => c2 == c1).Count >= 2).Distinct().ToList(); //выбираем все повторяющиеся символы, в независимости от строки в которой они находятся
//Проверяем если ли символ конца строки между первым и последним вхождением символа.
foreach (char c in chars)
if(buffer.IndexOf(Environment.NewLine, buffer.IndexOf(c), buffer.LastIndexOf(c) - buffer.IndexOf(c))>=0&&c!='\n'&&c!='\r') Console.WriteLine(c);

Гость

20 - 31.10.2014 - 10:58

19-LostDaemon > что ваша программа выведет при таком входном файле:
12 13 4
31 21 34
Есть так же подозрение на отображение пробела =)

Гость

21 - 31.10.2014 - 11:07

выводит 1234, но пробелы тоже пишет.

Можно просто добавить &&c!=' ' к условию в последней строке:

if(buffer.IndexOf(Environment.NewLine, buffer.IndexOf(c), buffer.LastIndexOf(c) - buffer.IndexOf(c))>=0&&c!='\n'&&c!='\r') Console.WriteLine(c);

Гость

22 - 31.10.2014 - 11:15

А еще лучше с самого начала сделать buffer=buffer.Replace(" ","");

Гость

23 - 31.10.2014 - 13:02

http://pastebin.com/ZcQBrJQE

Гость

24 - 31.10.2014 - 13:32

22-LostDaemon > в условии было про числа, а не символы И какой то уж слишком большой оверхед у вас ИМХО.=)

Гость

25 - 31.10.2014 - 14:15

22-Поскольку в задании было упоминание "в разных строках файла" я решил, что пример с числами- это всего лишь частный случай и работал с символами.

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

Гость

26 - 31.10.2014 - 14:48

25-LostDaemon > Ок, зачет =)
можно подробнее о подходе перебором и словарем? а то я чет не понимаю.

Гость

27 - 01.11.2014 - 02:16

Перебором со словарем:
1)Читаем в строку
2)Проходим последовательно все символы, помещая их в словарь Dictionary<char,int>, где Key-символ, Value-номер строки в которой он встретился.
3)Если находим символы конца строки, наращиваем счетчик номера строки.
4)Если символ уже есть в словаре и его Value не совпадает с текущим номером строки, то выводим этот символ в результат, а соответствующее этому символу Value в словаре меняем на -1. При значении Value=-1 обработку символа пропустить.

string input = File.ReadAllText("c:\\1\\1.txt");
Dictionary<char, int> Dict = new Dictionary<char, int>();//Словарь Key-символ Value-№строки где впервые встретился
int LineCounter = 0; //счетчик строк
foreach (char c in input) //перебираем символы
**
switch(c)
**
case '\r': break;
case '\n': LineCounter++; break; //конец строки - наращиваем счетчик строк
default:
int i=-1;
if (Dict.TryGetValue(c, out i)) //получаем номер строки первого вхождения символа, если таковое имело место
**
//если номер строки текущего символа не совпадает с номером в словаре и не равен флагу -1(см. далее) - значит нашли символ, повторяющийся в разных строках - выводим его в консоль , а значение value в словаре устанавливаем в -1, чтобы пропустить обработку этого символа в дальнейшем.
if (i != LineCounter && i != -1) ** Dict[c] = -1; Console.WriteLine(c); **
**
else
**
Dict.Add(c, LineCounter); //добавляем символ в словарь если еще не встречался
**
break;
**
**
Console.ReadLine();

Гость

28 - 07.11.2014 - 11:39

Мои 5 копеек
1. Считываем все в массив размером А х Б
2. Построчно проходим по массиву, оставляя только уникальные значения
3. Рассматриваем двухмерный массив А х Б как одномерный А*Б
4. Снова задействуем алгоритм, оставляющий только уникальные значения, с поправкой, что значения дублей еще и на экран вывести

Гость

29 - 07.11.2014 - 11:43

Поправка, "2. Построчно проходим по массиву, оставляя в каждой строке только уникальные значения"

Гость

30 - 08.11.2014 - 01:50

AlienX - от оно... 2 вариантты