Интересные задачи для программистов

D
На сайте с 18.12.2015
Offline
142
2031

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

Есть файл с таким содержимым (ссылка на полный файл):


[ {
"id": 47704,
"scores": 0.7003193510956659
},
{
"id": 9811,
"scores": 0.7147695018808078
}
]

Нужно написать потоковый декодер, который будет парсить файл, отфильтровать объекты, где scores > 0.7, и затем записать эти объекты в файл рядом (тоже потоково). Загружать весь файл полностью и распаковывать в массив нельзя. Изменять структуру файла из задачи нельзя. Выходной формат тоже JSON. Итоговая сортировка не важна. Язык не важен.

Разработка и поддержка высоконагруженных проектов.
O
На сайте с 30.09.2019
Offline
18
#1

Не уверен, что решение правильное. Просто, топ поддержать )


$.ajax({
url: "//0x.com.ua/task-1.json",
dataType: "json",
success: function (e) {
t($.map(e, function(e) {
if(e.scores > 0.7) {
return {
id: e.id,
scores: e.scores
}
}
}))
}
})
T7
На сайте с 19.09.2018
Offline
34
#2

<?php
header('content-type:text/plain');
$handle = fopen( '/var/web/aio/data/json', 'cb+' );
$str = ''; $read = false;
$t0 = microtime(true);
$i = 0;
$ii = 0;
while (!feof($handle)) {
$c = fread($handle, 1);
if($c=='{'){
$read = true;
}
if($read) {
$str.=$c;
}
if($c=='}') {
$a = json_decode($str);
$i++;
if( is_object($a) && $a->scores > 0.7){

$ii++;
$a->allobjcnt = $i;
$a->matchedobjcnt = $ii;
print_r($a);
}
$str = ''; $read = false;
}
}
echo sprintf("Timing: %0000001.4f sec", (microtime(true) - $t0)), "
######################################################
# /ru/forum/1032923
######################################################


";
fclose($handle);
?>

Про запись в результата файл сразу не заметил.

Но там несложно, если пустой просто пишем "[{json_encode найденного}]"

дальше идем в конец, находим позицию "]" и с этой позиции дописываем ",{json_encode найденного}]"

$p = fseek($handle, -1, SEEK_END);
$c = ''; $pos = ftell($handle);
while( $c!=']' ){
$c=fread( $handle , 1 );
$pos-=2;
fseek($handle, $pos);
}
S3
На сайте с 29.03.2012
Offline
221
#3


import json
import time

start = time.time()
with open('task-1.json') as data:
f = json.load(data)
print(len(f))
with open('task-1.json') as data:
content = data.read()
row = json.loads(content)
with open('res-task-1.json', 'w') as f:
f.write('[') for item in row:
if item.get('scores') >= 0.7:
f.write(json.dumps(item))
f.write(',')
f.write(']')
print(time.time()-start)

две строки тут лишние - толкь для подсчета времени

в среднем выполняется за 0.03 сек на core i5 quad

было 10000 строк стало 2995

T7
На сайте с 19.09.2018
Offline
34
#4
Sly32:
content = data.read()

В задаче запрещено грузить весь файл

danforth:
Загружать весь файл полностью и распаковывать в массив нельзя.
Z0
На сайте с 03.09.2009
Offline
730
#5

Задал бы я вам квест, да не хочу палиться 🤪 Но там чисто алгоритм, но до сих пор сложить его не могу, умишком слаб :p

S3
На сайте с 29.03.2012
Offline
221
#6
timo-71:
В задаче запрещено грузить весь файл

да, неправильно в таком случае мое решение

D
На сайте с 18.12.2015
Offline
142
#7

Sly32, на выходе не валидный json :) Да и вычитано у тебя все в память.

Мое решение на Go, как обычно - самое длинное https://play.golang.org/p/gWg-gqR-Xvi

file filtered successfully, took 22.997923ms
S3
На сайте с 29.03.2012
Offline
221
#8
danforth:
Sly32, на выходе не валидный json Да и вычитано у тебя все в память.

Да, вижу, но пока не нашел красивого решения. не нравиться мне идея читать посимвольно файл руками) С валидацией вроде знаю как решить. Пока роюсь, что там есть в питоне для таких случаев. В приницпе код что на го, что на пхп примерно одинаков будет по длине

Gerga
На сайте с 02.08.2015
Offline
89
#9
Sly32:
В приницпе код что на го, что на пхп примерно одинаков будет по длине

На php он может быть еще короче, если не читать посимвольно.


define('MINIMUM', 0.7);
define('DELIMER', '}');

$filepath_in = 'task-1.json';
$filepath_out = 'task-1-out.json';

$b = '';

$handle_in = fopen($filepath_in, 'r');

file_put_contents($filepath_out, '['); while (!feof($handle_in)) {
$line = stream_get_line($handle_in, 100, DELIMER);

$r = preg_match('/{(.*?)([0-9.]+)$/', $line, $matches);

if ($r && MINIMUM < $matches[2]) {
$line = $b . $matches[0] . DELIMER;
file_put_contents($filepath_out, $line, FILE_APPEND);
$b = ',';
}
}

file_put_contents($filepath_out, ']', FILE_APPEND);

fclose($handle_in);
VoV@
На сайте с 22.09.2007
Offline
196
#10

Вот решил простым перебором:


using Newtonsoft.Json;
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

namespace Searchengines
{
class Program
{

static void Main(string[] args)
{
var _sourceArrayItem = new List<char>();
var canRead = false;
var firstAppend = true;

using var sr = new StreamReader($"{Environment.CurrentDirectory}\\task-1.json");
using var sw = new FileStream($"{Environment.CurrentDirectory}\\result.json", FileMode.OpenOrCreate);

var terminalSymbol = Encoding.Default.GetBytes("["); sw.Write(terminalSymbol, 0, terminalSymbol.Length);

while (sr.Peek() >= 0)
{
var symbol = (char)sr.Read();
if (symbol == '{' || canRead)
{
_sourceArrayItem.Add(symbol);
canRead = true;
}
if (symbol == '}')
{
var item = new string(_sourceArrayItem.ToArray());
var parsedItem = JsonConvert.DeserializeObject<TaskItem>(item);

if (parsedItem.Scores > 0.7)
{
item = firstAppend ? item : $",{item}";
var buffer = Encoding.Default.GetBytes(item);
sw.Write(buffer, 0, buffer.Length);
sw.Flush();

firstAppend = false;
}

_sourceArrayItem = new List<char>();
canRead = false;
}
}

terminalSymbol = Encoding.Default.GetBytes("]");
sw.Write(terminalSymbol, 0, terminalSymbol.Length);
sw.Close();
}

public class TaskItem
{
public int Id { get; set; }
public double Scores { get; set; }
}
}
}

Если не грузить сразу в память всё, то ИМХО, только и перебором символов получится.

⭐ Разработка Андроид-приложений (Xamarin C#). ⭐ Разработка ASP.NET (WebForms, MVC, WebAPI, Core). ⭐ Цой жив!

Авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий