n***p
发帖数: 110 | 1 给一个json string。找出所有对应的key不重复的value。
比如输入以下string，找出所有“title"的value
{
"glossary":{
"title":"example",
"GlossDiv":{
"title":"S",
"GlossList":{
"GlossEntry":{
"ID":"SGML",
"SortAs":"SGML",
"title":"S",
"Acronym":"SGML",
"Abbrev":"ISO 8879:1986",
"GlossDef":{ "title": "S"},
"GlossSee":[{"title": "e.g."}, {"another": "etc"}]
}
}
}
}
}
输出要是：含"example"，"S"， ”e.g." 三个值的collection。
注意：这个json string只有一行, 我format了只是方便大家看。
希望各位牛人给出你认为最好的方案。我明天会post我自己的。 |
a*****e
发帖数: 1700 | 2 题目不是很严谨啊，如果 "title" 的值是个表，里面还有 "title" 怎么办？ |
n***p
发帖数: 110 | 3 嗯，要找出来的值只是string。如果title值是表，继续往里找。
【在 a*****e 的大作中提到】
: 题目不是很严谨啊，如果 "title" 的值是个表，里面还有 "title" 怎么办？
|
a*****e
发帖数: 1700 | 4 我先来一个 FP 方案，是用 Javascript 写的，可以用 node 运行。
https://pastebin.com/NbXkYEjC
定义都是一行，多数都是 boilerplate，或者说它们是通用函数，与题目无关。
与题目相关的逻辑只在于两个定义，addKey 和 collect。
不是很好懂的地方是 traverse 函数，也是这里唯一用到递归的函数。这种方法统称叫
做 recursion scheme，有兴趣的可以 google，也欢迎私信探讨。 |
n***p
发帖数: 110 | 5 谢谢！
你用的input是之前的，我后来改动了一下，json里面有array。
能测试一下新的input吗？
【在 a*****e 的大作中提到】
: 我先来一个 FP 方案，是用 Javascript 写的，可以用 node 运行。
: https://pastebin.com/NbXkYEjC
: 定义都是一行，多数都是 boilerplate，或者说它们是通用函数，与题目无关。
: 与题目相关的逻辑只在于两个定义，addKey 和 collect。
: 不是很好懂的地方是 traverse 函数，也是这里唯一用到递归的函数。这种方法统称叫
: 做 recursion scheme，有兴趣的可以 google，也欢迎私信探讨。
|
a*****e
发帖数: 1700 | 6 新 input 也没问题
【在 n***p 的大作中提到】
: 谢谢！
: 你用的input是之前的，我后来改动了一下，json里面有array。
: 能测试一下新的input吗？
|
n***p
发帖数: 110 | 7 好，那我先把你的solution存底：
const id = x => x
const keys = o => Object.keys(o)
const values = o => keys(o).map(x=>o[x])
const assign = (...o) => Object.assign({}, ...o)
const map = f => xs => xs.map(x => f(x));
const omap = f => o => {o = assign(o); map(x => o[x] = f(x,o[x]))(keys(o));
return o}
const triple = (f, g, h) => o => Array.isArray(o) ? f(o) : typeof(o) == '
object' ? g(o) : h(o)
const fmap = f => triple(map(f), omap((k,v)=>f(v)), id)
const traverse = h => x => h(fmap(traverse(h)))(x)
const concat = a => a.reduce((x,y)=>x.concat(y), [])
const addKey = k => x => triple(concat, o => concat(values(o)).concat(x[k] ?
[x[k]] : []), x => [])
const comp = (f, g) => x => f(x)(g(x))
const collect = k => traverse(h => comp(addKey(k),h))
const unique = x => [...new Set(x)]
const solve = k => x => unique(collect(k)(JSON.parse(x)))
x = '{"glossary":{"title":"example","GlossDiv":{"title":"S","GlossList":{"
GlossEntry":{"ID":"SGML","SortAs":"SGML","title":"S","Acronym":"SGML","
Abbrev":"ISO 8879:1986","GlossDef":{"title":"e.g."},"GlossSee":"markup"}}}}}'
console.log(solve('title')(x))
【在 a*****e 的大作中提到】
: 新 input 也没问题
|
T*******x
发帖数: 8565 | 8 这个代码看着很高大上啊。
：我先来一个 FP 方案，是用 Javascript 写的，可以用 node 运行。
： |
n***p
发帖数: 110 | 9 here you go, in clojure:
(def m (clojure.data.json/read-str
"{ "glossary":{ "title":"example", "GlossDiv":{ "title":"S", "GlossList":{ "
title":{ "ID":"SGML", "SortAs":"SGML", "title":"S", "Acronym":"SGML", "
Abbrev":"ISO 8879:1986", "GlossDef":{ "title": "S"}, "GlossSee":[{"title": "
e.g."}, {"another": "etc"}] } } } } }"
))
(->> (tree-seq #(or (map? %) (vector? %)) identity m)
(keep #(get % "title"))
(filter #(not (map? %)))
set
)
Test code in REPL:
>lein repl
user=> (use 'clojure.data.json)
user=>
(def m (clojure.data.json/read-str
#_=> "{ "glossary":{ "title":"e, "GlossSee":[{"title": "e.g."}, {"another"
", "Abbrev":"ISO 8879:1986", "GlossDef":{ "title": "S"}
#_=> ))
#'user/m
user=> (->> (tree-seq #(or (map? %) (vector? %)) identity m)
#_=> (keep #(get % "title"))
#_=> (filter #(not (map? %)))
#_=> set
#_=> )
#{"example" "S" "e.g."}
2 vs 0, FP FTW :) |
m****o
发帖数: 182 | 10 觉得正确的做法是边parse json边accumulate map
;
【在 n***p 的大作中提到】
: 好，那我先把你的solution存底：
: const id = x => x
: const keys = o => Object.keys(o)
: const values = o => keys(o).map(x=>o[x])
: const assign = (...o) => Object.assign({}, ...o)
: const map = f => xs => xs.map(x => f(x));
: const omap = f => o => {o = assign(o); map(x => o[x] = f(x,o[x]))(keys(o));
: return o}
: const triple = (f, g, h) => o => Array.isArray(o) ? f(o) : typeof(o) == '
: object' ? g(o) : h(o)
|
|
|
s*********y
发帖数: 6151 | 11 感觉挺简单啊 就是个recursive 一直往下找就好了 |
a*****e
发帖数: 1700 | 12 这种优化，其实应该交给编译器来做，虽然目前大多数都做不到。不过 Haskell/GHC
应该可以。
【在 m****o 的大作中提到】
: 觉得正确的做法是边parse json边accumulate map
:
: ;
|
d******c
发帖数: 2407 | 13 FP的特点就是避开那个复杂的包含一切的loop
一边parse一边做事，相比parse一遍，筛选一遍，加工一遍看起来节省一些扫描次数，
但是实际性能差别未必很大，最重要的是思维负担很大。
要在loop中一边扫描一边做事，就需要一直维护状态，例外情况会很复杂，如果要求变
化了会更复杂，而且很难一下子理解全部内容，过段时间自己都看不懂。
FP把动作抽象出来，每个动作都是库函数，不需要自己写，思维负担要小很多，需求变
化也容易调整。真要有性能瓶颈再根据具体情况去优化就是了。 |
s*********y
发帖数: 6151 | 14 就是个map reduce filter 别说的那么玄乎
【在 d******c 的大作中提到】
: FP的特点就是避开那个复杂的包含一切的loop
: 一边parse一边做事，相比parse一遍，筛选一遍，加工一遍看起来节省一些扫描次数，
: 但是实际性能差别未必很大，最重要的是思维负担很大。
: 要在loop中一边扫描一边做事，就需要一直维护状态，例外情况会很复杂，如果要求变
: 化了会更复杂，而且很难一下子理解全部内容，过段时间自己都看不懂。
: FP把动作抽象出来，每个动作都是库函数，不需要自己写，思维负担要小很多，需求变
: 化也容易调整。真要有性能瓶颈再根据具体情况去优化就是了。
|
d***a
发帖数: 13752 | 15 这个有意思。下面是pythod版本，程序存为match.py，输入存到input.txt，运行命令
是python match.py < input.txt。
import sys
import re
from sets import Set
pattern = "\"title\":\s*\"([\w\.]*)\""
titles = Set()
for line in sys.stdin:
match = re.search(pattern, line)
if match:
titles.add(match.group(1))
for title in titles:
print title |
a*****e
发帖数: 1700 | 16 一行有多个 title 这个就出错了。Writing your own parser is almost always
unnecessary, and error prone.
【在 d***a 的大作中提到】
: 这个有意思。下面是pythod版本，程序存为match.py，输入存到input.txt，运行命令
: 是python match.py < input.txt。
: import sys
: import re
: from sets import Set
: pattern = "\"title\":\s*\"([\w\.]*)\""
: titles = Set()
: for line in sys.stdin:
: match = re.search(pattern, line)
: if match:
|
a*****e
发帖数: 1700 | 17 用 tree-seq 有点 cheat 了。tree-seq 已经可以把 tree 扁平化成列表，接下来得工
作微乎其微啊
"
"
【在 n***p 的大作中提到】
: here you go, in clojure:
: (def m (clojure.data.json/read-str
: "{ "glossary":{ "title":"example", "GlossDiv":{ "title":"S", "GlossList":{ "
: title":{ "ID":"SGML", "SortAs":"SGML", "title":"S", "Acronym":"SGML", "
: Abbrev":"ISO 8879:1986", "GlossDef":{ "title": "S"}, "GlossSee":[{"title": "
: e.g."}, {"another": "etc"}] } } } } }"
: ))
: (->> (tree-seq #(or (map? %) (vector? %)) identity m)
: (keep #(get % "title"))
: (filter #(not (map? %)))
|
d***a
发帖数: 13752 | 18 If it meets the specification, then it is correct.
当然，写着好玩的东西，不用楼主去费神写个specification出来，呵呵。
【在 a*****e 的大作中提到】
: 一行有多个 title 这个就出错了。Writing your own parser is almost always
: unnecessary, and error prone.
|
n***p
发帖数: 110 | 19 It's not hard to write tree-seq, 不到10行code
https://cljs.github.io/api/cljs.core/tree-seq
【在 a*****e 的大作中提到】
: 用 tree-seq 有点 cheat 了。tree-seq 已经可以把 tree 扁平化成列表，接下来得工
: 作微乎其微啊
:
: "
: "
|
n***p
发帖数: 110 | 20 我有写注意事项，你没看到 ：)
【在 d***a 的大作中提到】
: If it meets the specification, then it is correct.
: 当然，写着好玩的东西，不用楼主去费神写个specification出来，呵呵。
|
|
|
d***a
发帖数: 13752 | 21
啊，我看的太快了。:) 下面这个版本可以满足要求。
import sys
import json
from sets import Set
# Define an object hook function to check title
def check_title(dct):
if "title" in dct and type(dct["title"]) == unicode:
titles.add(dct["title"])
return dct
# Load json string with the hook function
titles = Set()
json.load(sys.stdin, object_hook=check_title)
# Print out titles
for title in titles:
print title
【在 n***p 的大作中提到】
: 我有写注意事项，你没看到 ：)
|
n***p
发帖数: 110 | 22 好奇集合 titles怎么pass 到check_title function的。
另外这个好像不可以handle title对应的是个Json吧，比如原帖给的sample。
【在 d***a 的大作中提到】
:
: 啊，我看的太快了。:) 下面这个版本可以满足要求。
: import sys
: import json
: from sets import Set
: # Define an object hook function to check title
: def check_title(dct):
: if "title" in dct and type(dct["title"]) == unicode:
: titles.add(dct["title"])
: return dct
|
d***a
发帖数: 13752 | 23 从测试结果看应该是没有问题，下面是测试结果。这应该和Python的json模块的实现有
关。
$ python match2.py < input.txt
S
example
e.g.
【在 n***p 的大作中提到】
: 好奇集合 titles怎么pass 到check_title function的。
: 另外这个好像不可以handle title对应的是个Json吧，比如原帖给的sample。
|
d******c
发帖数: 2407 | 24 我用了很多这种方法，但是很久没用过map reduce
map reduce非常狭隘，你在实际中用到的场合没有那么多，尤其非大数据的情况。
但是这个方法本身很多时候可以用，比如这种filter，解析。跟map reduce基本没有关
系。map reduce不是一个好的概括。
【在 s*********y 的大作中提到】
: 就是个map reduce filter 别说的那么玄乎
|
n***p
发帖数: 110 | 25 你可能用的是旧的sample input，新的在有人提出特例后在原帖里更新过，不过也应该
好改。
今天又学习了，Python还有自动pass argument的功能
【在 d***a 的大作中提到】
: 从测试结果看应该是没有问题，下面是测试结果。这应该和Python的json模块的实现有
: 关。
: $ python match2.py < input.txt
: S
: example
: e.g.
|
d***a
发帖数: 13752 | 26 我应该是用了旧的测试输入。修改了code, 加了个子条件后，新测试也可以过了。
Python的轮子很多，碰到有现存轮子可用的时候，写代码确实很快。这个代码，就是让
json模块在每次识别到一个json对象时调用check_title函数，检查一下这个对象有没
有title这个key，有的话就加入集合中。
【在 n***p 的大作中提到】
: 你可能用的是旧的sample input，新的在有人提出特例后在原帖里更新过，不过也应该
: 好改。
: 今天又学习了，Python还有自动pass argument的功能
|
m****o
发帖数: 182 | 27 用了龙太子的fastparse, collect函数是答案。注意把代码中的[back slash]去掉。这
个解法边parse json边收集结果，效
果应该比先parse完json再处理对应的dictionary/map要好一点。
import fastparse.all._
val space = P( CharsWhileIn(" \[back slash]r\[back slash]n").? )
val digits = P( CharsWhileIn("0123456789"))
val exponent = P( CharIn("eE") ~ CharIn("+-").? ~ digits )
val fractional = P( "." ~ digits )
val integral = P( "0" | CharIn('1' to '9') ~ digits.? )
val number = P( CharIn("+-").? ~ integral ~ fractional.? ~ exponent.? ).
map(_ => Set.empty[String])
val `null` = P( "null" ).map(_ => Set.empty[String])
val `false` = P( "false" ).map(_ => Set.empty[String])
val `true` = P( "true" ).map(_ => Set.empty[String])
val hexDigit = P( CharIn('0'to'9', 'a'to'f', 'A'to'F') )
val unicodeEscape = P( "u" ~ hexDigit ~ hexDigit ~ hexDigit ~ hexDigit )
val escape = P( "\[back slash]\[back slash]" ~ (CharIn("\[back
slash]"/\[back slash]\[back slash]bfnrt") | unicodeEscape) )
val strChars = P( CharsWhile(!"\[back slash]"\[back slash]\[back slash]".
contains(_: Char)) )
val string =
P( space ~ "\[back slash]"" ~/ (strChars | escape).rep.! ~ "\[back slash
]"")
val stringValue = string.map(Set(_))
def pair = (string ~/ ":" ~/ (stringValue.map(Left(_)) | expr.map(Right(_)
))) map { case (k, v) =>
if (k == "title") v.fold(identity, identity)
else v.fold(_ => Set.empty[String], identity)
}
def obj =
P( "{" ~/ pair.rep(sep=",".~/) ~ space ~ "}").map(_.reduce(_ union _))
def array =
P( "[" ~/ expr.rep(sep=",".~/) ~ space ~ "]").map(_.reduce(_ union _))
def expr : Parser[Set[String]]= P(
space ~ (obj | array | stringValue.map(_ => Set.empty[String]) | `true`
| `false` | `null` | number) ~ space
)
def collect(json: String): Set[String] =
expr.parse(json) match {
case Success(set, _) => set
case _ => Set.empty
}
【在 n***p 的大作中提到】
: 给一个json string。找出所有对应的key不重复的value。
: 比如输入以下string，找出所有“title"的value
: {
: "glossary":{
: "title":"example",
: "GlossDiv":{
: "title":"S",
: "GlossList":{
: "GlossEntry":{
: "ID":"SGML",
|
n***p
发帖数: 110 | |
n******7
发帖数: 12463 | 29 贴个C#的，test通过
对json处理不熟，我其实感觉用正则表达式抓一下就好了？
---
Code
---
using System.Collections.Generic;
using System.Linq;
using Newtonsoft.Json.Linq;
namespace Mitbbs
{
public static class Utilities
{
public static IEnumerable FindUniqueValuesFromKey(string
json, string key) =>
ProcessJsonToken(JObject.Parse(json)).Where(x => x.Key == key).
Select(x => x.Value).Distinct();
private static IEnumerable<(string Key, string Value)>
ProcessJsonToken(JToken jToken)
{
switch (jToken)
{
case JProperty jProperty:
return ProcessJsonProperty(jProperty);
case JArray jArray:
return jArray.Children().Select(ProcessJsonToken).
SelectMany(x => x);
case JObject jObject:
return jObject.Properties().Select(ProcessJsonToken).
SelectMany(x => x);
default:
return new(string, string)[] { };
}
}
private static IEnumerable<(string Key, string Value)>
ProcessJsonProperty(JProperty jProperty)
{
switch (jProperty.Value.Type)
{
case JTokenType.String:
return new[] {(jProperty.Name, jProperty.Value.ToString(
))};
case JTokenType.Object:
case JTokenType.Property:
case JTokenType.Array:
return jProperty.Value.Children().Select(
ProcessJsonToken).SelectMany(x => x);
default:
return new (string, string)[] { };
}
}
}
}
---
Test
---
using Mitbbs;
using Xunit;
namespace Unittests
{
public class UtilitiesTests
{
private const string Json = @"{
'glossary':{
'title':'example',
'GlossDiv':{
'title':'S',
'GlossList':{
'title':{
'ID':'SGML',
'SortAs':'SGML',
'title':'S',
'Acronym':'SGML',
'Abbrev':'ISO 8879:1986',
'GlossDef':{ 'title': 'S'},
'GlossSee':[{'title': 'e.g.'}, {'another
': 'etc'}]
}
}
}
}
}";
[Fact]
public void FindUniqueValuesFromKey_AsExpected()
{
var expected = new[] { "example", "S", "e.g." };
Assert.Equal(expected, Utilities.FindUniqueValuesFromKey(Json, "
title"));
}
}
}
【在 n***p 的大作中提到】
: 所有答案里有OOP吗？
|
s*****V
发帖数: 21731 | 30 这玩意太简单了，有蛮力巧力能有多大区别？
【在 n***p 的大作中提到】
: 给一个json string。找出所有对应的key不重复的value。
: 比如输入以下string，找出所有“title"的value
: {
: "glossary":{
: "title":"example",
: "GlossDiv":{
: "title":"S",
: "GlossList":{
: "GlossEntry":{
: "ID":"SGML",
|
|
|
n***p
发帖数: 110 | 31 You can solve any problems in many ways.
The difference for me is I am lazy, I don't want to write long code.
【在 s*****V 的大作中提到】
: 这玩意太简单了，有蛮力巧力能有多大区别？
|
n***p
发帖数: 110 | 32 给一个json string。找出所有对应的key不重复的value。
比如输入以下string，找出所有“title"的value
{
"glossary":{
"title":"example",
"GlossDiv":{
"title":"S",
"GlossList":{
"title":{
"ID":"SGML",
"SortAs":"SGML",
"title":"S",
"Acronym":"SGML",
"Abbrev":"ISO 8879:1986",
"GlossDef":{ "title": "S"},
"GlossSee":[{"title": "e.g."}, {"another": "etc"}]
}
}
}
}
}
输出要是：含"example"，"S"， ”e.g." 三个值的collection。
注意：这个json string只有一行, 我format了只是方便大家看。
希望各位牛人给出你认为最好的方案。我明天会post我自己的。 |
a*****e
发帖数: 1700 | 33 题目不是很严谨啊，如果 "title" 的值是个表，里面还有 "title" 怎么办？ |
n***p
发帖数: 110 | 34 嗯，要找出来的值只是string。如果title值是表，继续往里找。
【在 a*****e 的大作中提到】
: 题目不是很严谨啊，如果 "title" 的值是个表，里面还有 "title" 怎么办？
|
a*****e
发帖数: 1700 | 35 我先来一个 FP 方案，是用 Javascript 写的，可以用 node 运行。
https://pastebin.com/NbXkYEjC
定义都是一行，多数都是 boilerplate，或者说它们是通用函数，与题目无关。
与题目相关的逻辑只在于两个定义，addKey 和 collect。
不是很好懂的地方是 traverse 函数，也是这里唯一用到递归的函数。这种方法统称叫
做 recursion scheme，有兴趣的可以 google，也欢迎私信探讨。 |
n***p
发帖数: 110 | 36 谢谢！
你用的input是之前的，我后来改动了一下，json里面有array。
能测试一下新的input吗？
【在 a*****e 的大作中提到】
: 我先来一个 FP 方案，是用 Javascript 写的，可以用 node 运行。
: https://pastebin.com/NbXkYEjC
: 定义都是一行，多数都是 boilerplate，或者说它们是通用函数，与题目无关。
: 与题目相关的逻辑只在于两个定义，addKey 和 collect。
: 不是很好懂的地方是 traverse 函数，也是这里唯一用到递归的函数。这种方法统称叫
: 做 recursion scheme，有兴趣的可以 google，也欢迎私信探讨。
|
a*****e
发帖数: 1700 | 37 新 input 也没问题
【在 n***p 的大作中提到】
: 谢谢！
: 你用的input是之前的，我后来改动了一下，json里面有array。
: 能测试一下新的input吗？
|
n***p
发帖数: 110 | 38 好，那我先把你的solution存底：
const id = x => x
const keys = o => Object.keys(o)
const values = o => keys(o).map(x=>o[x])
const assign = (...o) => Object.assign({}, ...o)
const map = f => xs => xs.map(x => f(x));
const omap = f => o => {o = assign(o); map(x => o[x] = f(x,o[x]))(keys(o));
return o}
const triple = (f, g, h) => o => Array.isArray(o) ? f(o) : typeof(o) == '
object' ? g(o) : h(o)
const fmap = f => triple(map(f), omap((k,v)=>f(v)), id)
const traverse = h => x => h(fmap(traverse(h)))(x)
const concat = a => a.reduce((x,y)=>x.concat(y), [])
const addKey = k => x => triple(concat, o => concat(values(o)).concat(x[k] ?
[x[k]] : []), x => [])
const comp = (f, g) => x => f(x)(g(x))
const collect = k => traverse(h => comp(addKey(k),h))
const unique = x => [...new Set(x)]
const solve = k => x => unique(collect(k)(JSON.parse(x)))
x = '{"glossary":{"title":"example","GlossDiv":{"title":"S","GlossList":{"
GlossEntry":{"ID":"SGML","SortAs":"SGML","title":"S","Acronym":"SGML","
Abbrev":"ISO 8879:1986","GlossDef":{"title":"e.g."},"GlossSee":"markup"}}}}}'
console.log(solve('title')(x))
【在 a*****e 的大作中提到】
: 新 input 也没问题
|
T*******x
发帖数: 8565 | 39 这个代码看着很高大上啊。
：我先来一个 FP 方案，是用 Javascript 写的，可以用 node 运行。
： |
n***p
发帖数: 110 | 40 here you go, in clojure:
(->> (tree-seq #(or (map? %) (vector? %)) identity m)
(keep #(get % "title"))
(filter #(not (map? %)))
set
)
Test code in REPL:
>lein repl
user=> (use 'clojure.data.json)
user=>
(def m (clojure.data.json/read-str
#_=> "{ "glossary":{ "title":"e, "GlossSee":[{"title": "e.g."}, {"another"
", "Abbrev":"ISO 8879:1986", "GlossDef":{ "title": "S"}
#_=> ))
#'user/m
user=> (->> (tree-seq #(or (map? %) (vector? %)) identity m)
#_=> (keep #(get % "title"))
#_=> (filter #(not (map? %)))
#_=> set
#_=> )
#{"example" "S" "e.g."}
2 vs 0, FP FTW :) |
|
|
m****o
发帖数: 182 | 41 觉得正确的做法是边parse json边accumulate map
;
【在 n***p 的大作中提到】
: 好，那我先把你的solution存底：
: const id = x => x
: const keys = o => Object.keys(o)
: const values = o => keys(o).map(x=>o[x])
: const assign = (...o) => Object.assign({}, ...o)
: const map = f => xs => xs.map(x => f(x));
: const omap = f => o => {o = assign(o); map(x => o[x] = f(x,o[x]))(keys(o));
: return o}
: const triple = (f, g, h) => o => Array.isArray(o) ? f(o) : typeof(o) == '
: object' ? g(o) : h(o)
|
s*********y
发帖数: 6151 | 42 感觉挺简单啊 就是个recursive 一直往下找就好了 |
a*****e
发帖数: 1700 | 43 这种优化，其实应该交给编译器来做，虽然目前大多数都做不到。不过 Haskell/GHC
应该可以。
【在 m****o 的大作中提到】
: 觉得正确的做法是边parse json边accumulate map
:
: ;
|
d******c
发帖数: 2407 | 44 FP的特点就是避开那个复杂的包含一切的loop
一边parse一边做事，相比parse一遍，筛选一遍，加工一遍看起来节省一些扫描次数，
但是实际性能差别未必很大，最重要的是思维负担很大。
要在loop中一边扫描一边做事，就需要一直维护状态，例外情况会很复杂，如果要求变
化了会更复杂，而且很难一下子理解全部内容，过段时间自己都看不懂。
FP把动作抽象出来，每个动作都是库函数，不需要自己写，思维负担要小很多，需求变
化也容易调整。真要有性能瓶颈再根据具体情况去优化就是了。 |
s*********y
发帖数: 6151 | 45 就是个map reduce filter 别说的那么玄乎
【在 d******c 的大作中提到】
: FP的特点就是避开那个复杂的包含一切的loop
: 一边parse一边做事，相比parse一遍，筛选一遍，加工一遍看起来节省一些扫描次数，
: 但是实际性能差别未必很大，最重要的是思维负担很大。
: 要在loop中一边扫描一边做事，就需要一直维护状态，例外情况会很复杂，如果要求变
: 化了会更复杂，而且很难一下子理解全部内容，过段时间自己都看不懂。
: FP把动作抽象出来，每个动作都是库函数，不需要自己写，思维负担要小很多，需求变
: 化也容易调整。真要有性能瓶颈再根据具体情况去优化就是了。
|
d***a
发帖数: 13752 | 46 这个有意思。下面是pythod版本，程序存为match.py，输入存到input.txt，运行命令
是python match.py < input.txt。
import sys
import re
from sets import Set
pattern = "\"title\":\s*\"([\w\.]*)\""
titles = Set()
for line in sys.stdin:
match = re.search(pattern, line)
if match:
titles.add(match.group(1))
for title in titles:
print title |
a*****e
发帖数: 1700 | 47 一行有多个 title 这个就出错了。Writing your own parser is almost always
unnecessary, and error prone.
【在 d***a 的大作中提到】
: 这个有意思。下面是pythod版本，程序存为match.py，输入存到input.txt，运行命令
: 是python match.py < input.txt。
: import sys
: import re
: from sets import Set
: pattern = "\"title\":\s*\"([\w\.]*)\""
: titles = Set()
: for line in sys.stdin:
: match = re.search(pattern, line)
: if match:
|
a*****e
发帖数: 1700 | 48 用 tree-seq 有点 cheat 了。tree-seq 已经可以把 tree 扁平化成列表，接下来得工
作微乎其微啊
"
"
【在 n***p 的大作中提到】
: here you go, in clojure:
: (->> (tree-seq #(or (map? %) (vector? %)) identity m)
: (keep #(get % "title"))
: (filter #(not (map? %)))
: set
: )
: Test code in REPL:
: >lein repl
: user=> (use 'clojure.data.json)
: user=>
|
d***a
发帖数: 13752 | 49 If it meets the specification, then it is correct.
当然，写着好玩的东西，不用楼主去费神写个specification出来，呵呵。
【在 a*****e 的大作中提到】
: 一行有多个 title 这个就出错了。Writing your own parser is almost always
: unnecessary, and error prone.
|
n***p
发帖数: 110 | 50 It's not hard to write tree-seq, 不到10行code
https://cljs.github.io/api/cljs.core/tree-seq
【在 a*****e 的大作中提到】
: 用 tree-seq 有点 cheat 了。tree-seq 已经可以把 tree 扁平化成列表，接下来得工
: 作微乎其微啊
:
: "
: "
|
|
|
n***p
发帖数: 110 | 51 我有写注意事项，你没看到 ：)
【在 d***a 的大作中提到】
: If it meets the specification, then it is correct.
: 当然，写着好玩的东西，不用楼主去费神写个specification出来，呵呵。
|
d***a
发帖数: 13752 | 52
啊，我看的太快了。:) 下面这个版本可以满足要求。
import sys
import json
from sets import Set
# Define an object hook function to check title
def check_title(dct):
if "title" in dct and type(dct["title"]) == unicode:
titles.add(dct["title"])
return dct
# Load json string with the hook function
titles = Set()
json.load(sys.stdin, object_hook=check_title)
# Print out titles
for title in titles:
print title
【在 n***p 的大作中提到】
: 我有写注意事项，你没看到 ：)
|
n***p
发帖数: 110 | 53 好奇集合 titles怎么pass 到check_title function的。
另外这个好像不可以handle title对应的是个Json吧，比如原帖给的sample。
【在 d***a 的大作中提到】
:
: 啊，我看的太快了。:) 下面这个版本可以满足要求。
: import sys
: import json
: from sets import Set
: # Define an object hook function to check title
: def check_title(dct):
: if "title" in dct and type(dct["title"]) == unicode:
: titles.add(dct["title"])
: return dct
|
d***a
发帖数: 13752 | 54 从测试结果看应该是没有问题，下面是测试结果。这应该和Python的json模块的实现有
关。
$ python match2.py < input.txt
S
example
e.g.
【在 n***p 的大作中提到】
: 好奇集合 titles怎么pass 到check_title function的。
: 另外这个好像不可以handle title对应的是个Json吧，比如原帖给的sample。
|
d******c
发帖数: 2407 | 55 我用了很多这种方法，但是很久没用过map reduce
map reduce非常狭隘，你在实际中用到的场合没有那么多，尤其非大数据的情况。
但是这个方法本身很多时候可以用，比如这种filter，解析。跟map reduce基本没有关
系。map reduce不是一个好的概括。
【在 s*********y 的大作中提到】
: 就是个map reduce filter 别说的那么玄乎
|
n***p
发帖数: 110 | 56 你可能用的是旧的sample input，新的在有人提出特例后在原帖里更新过，不过也应该
好改。
今天又学习了，Python还有自动pass argument的功能
【在 d***a 的大作中提到】
: 从测试结果看应该是没有问题，下面是测试结果。这应该和Python的json模块的实现有
: 关。
: $ python match2.py < input.txt
: S
: example
: e.g.
|
d***a
发帖数: 13752 | 57 我应该是用了旧的测试输入。修改了code, 加了个子条件后，新测试也可以过了。
Python的轮子很多，碰到有现存轮子可用的时候，写代码确实很快。这个代码，就是让
json模块在每次识别到一个json对象时调用check_title函数，检查一下这个对象有没
有title这个key，有的话就加入集合中。
【在 n***p 的大作中提到】
: 你可能用的是旧的sample input，新的在有人提出特例后在原帖里更新过，不过也应该
: 好改。
: 今天又学习了，Python还有自动pass argument的功能
|
m****o
发帖数: 182 | 58 用了龙太子的fastparse, collect函数是答案。注意把代码中的[back slash]去掉。这
个解法边parse json边收集结果，效
果应该比先parse完json再处理对应的dictionary/map要好一点。
import fastparse.all._
val space = P( CharsWhileIn(" \[back slash]r\[back slash]n").? )
val digits = P( CharsWhileIn("0123456789"))
val exponent = P( CharIn("eE") ~ CharIn("+-").? ~ digits )
val fractional = P( "." ~ digits )
val integral = P( "0" | CharIn('1' to '9') ~ digits.? )
val number = P( CharIn("+-").? ~ integral ~ fractional.? ~ exponent.? ).
map(_ => Set.empty[String])
val `null` = P( "null" ).map(_ => Set.empty[String])
val `false` = P( "false" ).map(_ => Set.empty[String])
val `true` = P( "true" ).map(_ => Set.empty[String])
val hexDigit = P( CharIn('0'to'9', 'a'to'f', 'A'to'F') )
val unicodeEscape = P( "u" ~ hexDigit ~ hexDigit ~ hexDigit ~ hexDigit )
val escape = P( "\[back slash]\[back slash]" ~ (CharIn("\[back
slash]"/\[back slash]\[back slash]bfnrt") | unicodeEscape) )
val strChars = P( CharsWhile(!"\[back slash]"\[back slash]\[back slash]".
contains(_: Char)) )
val string =
P( space ~ "\[back slash]"" ~/ (strChars | escape).rep.! ~ "\[back slash
]"")
val stringValue = string.map(Set(_))
def pair = (string ~/ ":" ~/ (stringValue.map(Left(_)) | expr.map(Right(_)
))) map { case (k, v) =>
if (k == "title") v.fold(identity, identity)
else v.fold(_ => Set.empty[String], identity)
}
def obj =
P( "{" ~/ pair.rep(sep=",".~/) ~ space ~ "}").map(_.reduce(_ union _))
def array =
P( "[" ~/ expr.rep(sep=",".~/) ~ space ~ "]").map(_.reduce(_ union _))
def expr : Parser[Set[String]]= P(
space ~ (obj | array | stringValue.map(_ => Set.empty[String]) | `true`
| `false` | `null` | number) ~ space
)
def collect(json: String): Set[String] =
expr.parse(json) match {
case Success(set, _) => set
case _ => Set.empty
}
【在 n***p 的大作中提到】
: 给一个json string。找出所有对应的key不重复的value。
: 比如输入以下string，找出所有“title"的value
: {
: "glossary":{
: "title":"example",
: "GlossDiv":{
: "title":"S",
: "GlossList":{
: "title":{
: "ID":"SGML",
|
n***p
发帖数: 110 | |
n******7
发帖数: 12463 | 60 贴个C#的，test通过
对json处理不熟，我其实感觉用正则表达式抓一下就好了？
---
Code
---
using System.Collections.Generic;
using System.Linq;
using Newtonsoft.Json.Linq;
namespace Mitbbs
{
public static class Utilities
{
public static IEnumerable FindUniqueValuesFromKey(string
json, string key) =>
ProcessJsonToken(JObject.Parse(json)).Where(x => x.Key == key).
Select(x => x.Value).Distinct();
private static IEnumerable<(string Key, string Value)>
ProcessJsonToken(JToken jToken)
{
switch (jToken)
{
case JProperty jProperty:
return ProcessJsonProperty(jProperty);
case JArray jArray:
return jArray.Children().Select(ProcessJsonToken).
SelectMany(x => x);
case JObject jObject:
return jObject.Properties().Select(ProcessJsonToken).
SelectMany(x => x);
default:
return new(string, string)[] { };
}
}
private static IEnumerable<(string Key, string Value)>
ProcessJsonProperty(JProperty jProperty)
{
switch (jProperty.Value.Type)
{
case JTokenType.String:
return new[] {(jProperty.Name, jProperty.Value.ToString(
))};
case JTokenType.Object:
case JTokenType.Property:
case JTokenType.Array:
return jProperty.Value.Children().Select(
ProcessJsonToken).SelectMany(x => x);
default:
return new (string, string)[] { };
}
}
}
}
---
Test
---
using Mitbbs;
using Xunit;
namespace Unittests
{
public class UtilitiesTests
{
private const string Json = @"{
'glossary':{
'title':'example',
'GlossDiv':{
'title':'S',
'GlossList':{
'title':{
'ID':'SGML',
'SortAs':'SGML',
'title':'S',
'Acronym':'SGML',
'Abbrev':'ISO 8879:1986',
'GlossDef':{ 'title': 'S'},
'GlossSee':[{'title': 'e.g.'}, {'another
': 'etc'}]
}
}
}
}
}";
[Fact]
public void FindUniqueValuesFromKey_AsExpected()
{
var expected = new[] { "example", "S", "e.g." };
Assert.Equal(expected, Utilities.FindUniqueValuesFromKey(Json, "
title"));
}
}
}
【在 n***p 的大作中提到】
: 所有答案里有OOP吗？
|
|
|
s*****V
发帖数: 21731 | 61 这玩意太简单了，有蛮力巧力能有多大区别？
【在 n***p 的大作中提到】
: 给一个json string。找出所有对应的key不重复的value。
: 比如输入以下string，找出所有“title"的value
: {
: "glossary":{
: "title":"example",
: "GlossDiv":{
: "title":"S",
: "GlossList":{
: "title":{
: "ID":"SGML",
|
n***p
发帖数: 110 | 62 You can solve any problems in many ways.
The difference for me is I am lazy, I don't want to write long code.
【在 s*****V 的大作中提到】
: 这玩意太简单了，有蛮力巧力能有多大区别？
|
T*******x
发帖数: 8565 | 63 这两天碰到一个json问题，有了答案，突然想起本版的这道题，就把自己的答案post上
来。我这个用到了一个“json path”的概念，和xpath差不多，和其他的tree path也
差不多。这算是解决此类问题的一个一般性方法吧。 |
T*******x
发帖数: 8565 | 64 再来一个SQL solution，纯SQL :)
这个是SQL Server的JSON功能。
用了recursive CTE，这段时间用recursive CTE上瘾了。不过没在production中用过。
SQL “LIKE” string方括号要escape，只有左方括号，右方括号不需要。
【在 T*******x 的大作中提到】
: 这两天碰到一个json问题，有了答案，突然想起本版的这道题，就把自己的答案post上
: 来。我这个用到了一个“json path”的概念，和xpath差不多，和其他的tree path也
: 差不多。这算是解决此类问题的一个一般性方法吧。
|
T*******x
发帖数: 8565 | 65 无recursion必须来一个啊。前锋推进法。
【在 T*******x 的大作中提到】
: 这两天碰到一个json问题，有了答案，突然想起本版的这道题，就把自己的答案post上
: 来。我这个用到了一个“json path”的概念，和xpath差不多，和其他的tree path也
: 差不多。这算是解决此类问题的一个一般性方法吧。
|
T*******x
发帖数: 8565 | 66 那既然如此，标准recursion替代法也必须来一个啊：栈法。
【在 T*******x 的大作中提到】
: 无recursion必须来一个啊。前锋推进法。
|
n***p
发帖数: 110 | 67 不重复value，你还得过滤一道
【在 T*******x 的大作中提到】
: 那既然如此，标准recursion替代法也必须来一个啊：栈法。
|
T*******x
发帖数: 8565 | 68 说的对。
【在 n***p 的大作中提到】
: 不重复value，你还得过滤一道
|
