#设备发现协议

发送如下XML消息。服务端会返回设备信息

1
2
3
4
5
6
7
8
9
10
11
12
13
<?xml version="1.0" encoding="utf-8"?>
<Envelope xmlns:dn="http://www.onvif.org/ver10/network/wsdl" xmlns="http://www.w3.org/2003/05/soap-envelope">
<Header>
<wsa:MessageID xmlns:wsa="http://schemas.xmlsoap.org/ws/2004/08/addressing">uuid:6d09a111-2662-49de-ba92-b429b35ec189</wsa:MessageID>
<wsa:To xmlns:wsa="http://schemas.xmlsoap.org/ws/2004/08/addressing">urn:schemas-xmlsoap-org:ws:2005:04:discovery</wsa:To>
<wsa:Action xmlns:wsa="http://schemas.xmlsoap.org/ws/2004/08/addressing">http://schemas.xmlsoap.org/ws/2005/04/discovery/Probe</wsa:Action>
</Header>
<Body>
<Probe xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns="http://schemas.xmlsoap.org/ws/2005/04/discovery">
<Types>dn:NetworkVideoTransmitter</Types><Scopes />
</Probe>
</Body>
</Envelope>

##erlang 脚本

首先需要向239.255.255.250:3702 以UDP协议发送XML消息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
% udp Client 
client(Port,Msg) ->
{ok, Socket} = gen_udp:open(0, [binary]),
io:format("client opened socket=~p~n",[Socket]),
ok = gen_udp:send(Socket, Port, 3702, Msg ),
Value = udp_recieve(Socket,[]),

gen_udp:close(Socket),
Value.
%
udp_recieve(Sock,Value)->
receive
{udp, Sock, _, _, Bin} ->
%io:format("client received:~p~n",[Bin]),
udp_recieve(Sock,[Bin]++Value)
after 500 ->
Value
end.

##XML解析
发送完消息后,接收服务端的消息,然后收到新的XML文件。使用erlang 的xmerl_scan 模块进行解析。解析完在编写脚本来获取需要的信息。

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
%% 从[xmlText] 中提取path 和 value 
%% Tuple: xmlText ,Res:[]
%% get path and value from xmlText
get_info([],Res) ->
Res;
get_info([Tuple|R],Res)->
case Tuple of
#xmlText{parents = Parents,value = Value}
-> get_info(R,Res++[{Parents,Value}]);
_Else->
Res
end.
%% 从xmlElement 根据节点名提取 子节点[xmlElement]
%%Tuple : xmlElement, Node : String
search(Tuple,Node) when is_tuple(Tuple) ->
case Tuple of
#xmlElement{nsinfo = {_, Node}} ->
#xmlElement{content=Res}=Tuple,
Res;
#xmlElement{content= Children } ->
search(Children,Node,[]);
_Else ->
[]
end.
search([],_Node,Res)-> Res;
search([Tuple|R],Node,Res) ->
search(R,Node,Res ++ search(Tuple,Node)).

反馈消息格式

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
 <?xml version="1.0" encoding="UTF-8"?>
<env:Envelope xmlns:env="http://www.w3.org/2003/05/soap-envelope" xmlns:soapenc="http://www.w3.org/2003/05/soap-encoding" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:tt="http://www.onvif.org/ver10/schema" xmlns:tds="http://www.onvif.org/ver10/device/wsdl" xmlns:trt="http://www.onvif.org/ver10/media/wsdl" xmlns:timg="http://www.onvif.org/ver20/imaging/wsdl" xmlns:tev="http://www.onvif.org/ver10/events/wsdl" xmlns:tptz="http://www.onvif.org/ver20/ptz/wsdl" xmlns:tan="http://www.onvif.org/ver20/analytics/wsdl" xmlns:tst="http://www.onvif.org/ver10/storage/wsdl" xmlns:ter="http://www.onvif.org/ver10/error" xmlns:dn="http://www.onvif.org/ver10/network/wsdl" xmlns:tns1="http://www.onvif.org/ver10/topics" xmlns:tmd="http://www.onvif.org/ver10/deviceIO/wsdl" xmlns:wsdl="http://schemas.xmlsoap.org/wsdl" xmlns:wsoap12="http://schemas.xmlsoap.org/wsdl/soap12" xmlns:http="http://schemas.xmlsoap.org/wsdl/http" xmlns:d="http://schemas.xmlsoap.org/ws/2005/04/discovery" xmlns:wsadis="http://schemas.xmlsoap.org/ws/2004/08/addressing" xmlns:xop="http://www.w3.org/2004/08/xop/include" xmlns:wsnt="http://docs.oasis-open.org/wsn/b-2" xmlns:wsa="http://www.w3.org/2005/08/addressing" xmlns:wstop="http://docs.oasis-open.org/wsn/t-1" xmlns:wsrf-bf="http://docs.oasis-open.org/wsrf/bf-2" xmlns:wsntw="http://docs.oasis-open.org/wsn/bw-2" xmlns:wsrf-rw="http://docs.oasis-open.org/wsrf/rw-2" xmlns:wsaw="http://www.w3.org/2006/05/addressing/wsdl" xmlns:wsrf-r="http://docs.oasis-open.org/wsrf/r-2" xmlns:tnsn="http://www.eventextension.com/2011/event/topics"><env:Header><wsadis:MessageID>urn:uuid:ef7a28dc-1dd1-11b2-8199-8ce748e18e8a</wsadis:MessageID>
<wsadis:RelatesTo>uuid:7554cb93-bb81-4379-8eb2-c10f4bb259b1</wsadis:RelatesTo>
<wsadis:To>http://schemas.xmlsoap.org/ws/2004/08/addressing/role/anonymous</wsadis:To>
<wsadis:Action>http://schemas.xmlsoap.org/ws/2005/04/discovery/ProbeMatches</wsadis:Action>
<d:AppSequence InstanceId="1464710418" MessageNumber="1402"/>
</env:Header>
<env:Body><d:ProbeMatches><d:ProbeMatch><wsadis:EndpointReference><wsadis:Address>urn:uuid:ef7a28dc-1dd1-11b2-8199-8ce748e18e8a</wsadis:Address>
</wsadis:EndpointReference>
<d:Types>dn:NetworkVideoTransmitter tds:Device</d:Types>
<d:Scopes>onvif://www.onvif.org/type/video_encoder onvif://www.onvif.org/type/ptz onvif://www.onvif.org/type/audio_encoder onvif://www.onvif.org/location/ onvif://www.onvif.org/hardware/icamera8001 onvif://www.onvif.org/name/icamera8001 onvif://www.onvif.org/Profile/Streaming</d:Scopes>
<d:XAddrs>http://192.168.1.18/onvif/device_service</d:XAddrs>
<d:MetadataVersion>10</d:MetadataVersion>
</d:ProbeMatch>
</d:ProbeMatches>
</env:Body>
</env:Envelope>
<?xml version="1.0" encoding="UTF-8"?>
<env:Envelope xmlns:env="http://www.w3.org/2003/05/soap-envelope" xmlns:soapenc="http://www.w3.org/2003/05/soap-encoding" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:tt="http://www.onvif.org/ver10/schema" xmlns:tds="http://www.onvif.org/ver10/device/wsdl" xmlns:trt="http://www.onvif.org/ver10/media/wsdl" xmlns:timg="http://www.onvif.org/ver20/imaging/wsdl" xmlns:tev="http://www.onvif.org/ver10/events/wsdl" xmlns:tptz="http://www.onvif.org/ver20/ptz/wsdl" xmlns:tan="http://www.onvif.org/ver20/analytics/wsdl" xmlns:tst="http://www.onvif.org/ver10/storage/wsdl" xmlns:ter="http://www.onvif.org/ver10/error" xmlns:dn="http://www.onvif.org/ver10/network/wsdl" xmlns:tns1="http://www.onvif.org/ver10/topics" xmlns:tmd="http://www.onvif.org/ver10/deviceIO/wsdl" xmlns:wsdl="http://schemas.xmlsoap.org/wsdl" xmlns:wsoap12="http://schemas.xmlsoap.org/wsdl/soap12" xmlns:http="http://schemas.xmlsoap.org/wsdl/http" xmlns:d="http://schemas.xmlsoap.org/ws/2005/04/discovery" xmlns:wsadis="http://schemas.xmlsoap.org/ws/2004/08/addressing" xmlns:xop="http://www.w3.org/2004/08/xop/include" xmlns:wsnt="http://docs.oasis-open.org/wsn/b-2" xmlns:wsa="http://www.w3.org/2005/08/addressing" xmlns:wstop="http://docs.oasis-open.org/wsn/t-1" xmlns:wsrf-bf="http://docs.oasis-open.org/wsrf/bf-2" xmlns:wsntw="http://docs.oasis-open.org/wsn/bw-2" xmlns:wsrf-rw="http://docs.oasis-open.org/wsrf/rw-2" xmlns:wsaw="http://www.w3.org/2006/05/addressing/wsdl" xmlns:wsrf-r="http://docs.oasis-open.org/wsrf/r-2" xmlns:tnsn="http://www.eventextension.com/2011/event/topics"><env:Header><wsadis:MessageID>urn:uuid:ef7a28dc-1dd1-11b2-8199-8ce748e18e8a</wsadis:MessageID>
<wsadis:RelatesTo>uuid:6d09a111-2662-49de-ba92-b429b35ec189</wsadis:RelatesTo>
<wsadis:To>http://schemas.xmlsoap.org/ws/2004/08/addressing/role/anonymous</wsadis:To>
<wsadis:Action>http://schemas.xmlsoap.org/ws/2005/04/discovery/ProbeMatches</wsadis:Action>
<d:AppSequence InstanceId="1464710418" MessageNumber="1403"/>
</env:Header>
<env:Body><d:ProbeMatches><d:ProbeMatch><wsadis:EndpointReference><wsadis:Address>urn:uuid:ef7a28dc-1dd1-11b2-8199-8ce748e18e8a</wsadis:Address>
</wsadis:EndpointReference>
<d:Types>dn:NetworkVideoTransmitter tds:Device</d:Types>
<d:Scopes>onvif://www.onvif.org/type/video_encoder onvif://www.onvif.org/type/ptz onvif://www.onvif.org/type/audio_encoder onvif://www.onvif.org/location/ onvif://www.onvif.org/hardware/icamera8001 onvif://www.onvif.org/name/icamera8001 onvif://www.onvif.org/Profile/Streaming</d:Scopes>
<d:XAddrs>http://192.168.1.18/onvif/device_service</d:XAddrs>
<d:MetadataVersion>10</d:MetadataVersion>
</d:ProbeMatch>
</d:ProbeMatches>
</env:Body>
</env:Envelope>

##完整代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
%%%-------------------------------------------------------------------
%%% @author PC
%%% @copyright (C) 2016, <COMPANY>
%%% @doc
%%%
%%% @end
%%% Created : 30. 五月 2016 11:23
%%%-------------------------------------------------------------------
-module(xmlparser).
-author("PC").
-include_lib("xmerl/include/xmerl.hrl").
-include_lib("xmerl/include/xmerl_xpath.hrl").
-include_lib("xmerl/include/xmerl_xsd.hrl").
-include_lib("eunit/include/eunit.hrl").
-export([main/1,get_info/2,search/2]).


main(_v) ->
{ok, Req } = file:read_file("c:/erl/soap-master/uri.xml"),
Recv=client("239.255.255.250",Req),
Fun=fun F([Xml|R])->
io:format("get xml ~n"),
{Doc,_} = xmerl_scan:string(binary_to_list(Xml)),
get_info(search(Doc,"XAddrs"),[])++F(R);
F([])->[] end,
io:format("~p~n",[Fun(Recv)]).

% Client code
client(Port,Msg) ->
{ok, Socket} = gen_udp:open(0, [binary]),
io:format("client opened socket=~p~n",[Socket]),
ok = gen_udp:send(Socket, Port, 3702, Msg ),
Value = udp_recieve(Socket,[]),

gen_udp:close(Socket),
Value.

udp_recieve(Sock,Value)->
receive
{udp, Sock, _, _, Bin} ->
%io:format("client received:~p~n",[Bin]),
udp_recieve(Sock,[Bin]++Value)
after 500 ->
Value
end.

genera_path(Paths,NS)->% Paths: list() ,NS : namespace
lists:flatmap(fun(Item)-> "/"++NS++":"++Item end,Paths).
%%get ns from xmlnode
get_env(Xml_ns,Url) -> %Xml_ns : xmlElement, Url: atom()
List=element(3,Xml_ns),
lists:filter(fun(Raw) -> case Raw of
{_,Url } -> true;
_Else-> false end end, List).
%% Tuple: xmlText ,Res:[]
%% get path and value from xmlText
get_info([],Res) ->
Res;
get_info([Tuple|R],Res)->
case Tuple of
#xmlText{parents = Parents,value = Value}
-> get_info(R,Res++[{Parents,Value}]);
_Else->
Res
end.
%%Tuple : xmlElement, Node : String
search(Tuple,Node) when is_tuple(Tuple) ->
case Tuple of
#xmlElement{nsinfo = {_, Node}} ->
#xmlElement{content=Res}=Tuple,
Res;
#xmlElement{content= Children } ->
search(Children,Node,[]);
_Else ->
[]
end.
search([],_Node,Res)-> Res;
search([Tuple|R],Node,Res) ->
search(R,Node,Res ++ search(Tuple,Node)).

有这么一道面试题:

找出未知单链表中点元素。

市面上有2种方法:

  1. 先遍历算出总长度为length,再遍历length/2个元素。
  2. 使用快慢指针。快指针步长为2,慢指针为1。快指针到达链表末端时,慢指针正好为中点元素。

然而这2种方法本质上没有差别。

###废话不说先上结果:

0.00027776 s : find_mid 循环法
0.000276798 s : find_mid_1 双指针
2.81981 s : find_mid 提高指针取得下一个元素的代价
2.81391 s : find_mid_1

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <thread>
#include <sys/timeb.h>
#include <time.h>
#include <windows.h>
using namespace std;
class list {
private:
list *next = nullptr;

public:
int m_d;
list* add(list* p) { next = p; return p; }
list* get_next() { Sleep(delay); return next; }
static int delay;
};
int list::delay = 0;
list* find_mid(list* ptr)
{
int len = 0;
list *p_start = ptr;
while (true)
{
if (!p_start)
break;
len++;
p_start = p_start->get_next();
}
len /= 2; p_start = ptr;
while (len--)
{
p_start = p_start->get_next();
}
return p_start;
}
list* find_mid_1(list* ptr)
{
list *p_s1 = ptr, *p_s2 = ptr;
while (p_s2=p_s2->get_next())
{
p_s2 = p_s2->get_next();
if (!p_s2)
break;
p_s1 = p_s1->get_next();
}
return p_s1;
}
#define cal_time(fun,ptr) {\
QueryPerformanceCounter(&startCount);\
fun(ptr);\
QueryPerformanceCounter(&endCount);\
double elapsed = (double)(endCount.QuadPart - startCount.QuadPart) / freq.QuadPart;\
cout << elapsed<<" s : "<< #fun << endl;}

int main()
{
int c = 1*1000;
list * start = new list,*p;
p = start;
while (c--)
{
p = p->add(new list);
p->m_d = c;
}
LARGE_INTEGER startCount;
LARGE_INTEGER endCount;
LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);
_ASSERT(find_mid_1(start) == find_mid(start));
cal_time(find_mid, start);
cal_time(find_mid_1, start);
list::delay = 1;

cal_time(find_mid, start);
cal_time(find_mid_1, start);
return 0;
}

#分析
其实这2种方法都是O(n),使用大O表示法不够精确,这种简单的算法直接数一下next的调用次数就可以知道都是1.5*len个get_next().find_mid_1 唯一的优势就是少用了一个 int len。所以性能提升实在少的可怜。

#下面给出正确的方案
思路:其实也是用到了2个指针,其中一个走过的路程是另一个的1/2。但千万不要使用一个+1另一个+2。而是在前一个指针遍历的时候保存下来给另一个指针。

##原理:
虽然我们不能预知链表的长度,但是我们可以预期

前一个指针移动了n步时,将这个值赋值给后一个指针,然后预期前一个指针能访问到2n,如果预期达成,那么继续开展预期。如果预期失败,那么中点为上一次预期成功的点再移动 c/2步。

##分析:
上一次预期成功的点就是节约计算的关键。

最好情况为:预期成功了,然后链表也到底了。

最差情况为:链表长度为2^n-1。上一次预期成功的点为(2^(n-2))然后还要再走(2^(n-2))步。

当然如果增加期望点,性能还有望提升。

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
list* find_mid_2(list* ptr)
{
list *p_s1 = ptr, *p_s2 = ptr, *tmp= ptr;
int d = 1,t=1;
int i = 0;
while (true)
{

tmp = p_s2;
for (int c=0; i < d; i++,c++)
{
p_s2 = p_s2->get_next();
if (!p_s2)
{
int len = c / 2;
while (len--)
{
p_s1 = p_s1->get_next();
}
return p_s1;
}
}
d *= 2;
p_s1 = tmp;
}
return p_s1;
}

来看效果吧

最好情况
0.608294 s : find_mid
0.612391 s : find_mid_1
0.404288 s : find_mid_2

最差情况
0.604105 s : find_mid
0.600299 s : find_mid_1
0.502341 s : find_mid_2

我估算需要(1,1.25)n个get_next()操作。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <thread>
#include <sys/timeb.h>
#include <time.h>
#include <windows.h>
#include <list>
#include <queue>
#include <map>
using namespace std;
typedef list<int> mlist;
#define cal_time(fun,ptr) {\
QueryPerformanceCounter(&startCount);\
fun(ptr);\
QueryPerformanceCounter(&endCount);\
double elapsed = (double)(endCount.QuadPart - startCount.QuadPart) / freq.QuadPart;\
cout << elapsed<<" s : "<< #fun << endl;}

class stage {
public:
mlist* msrc;
map<int, mlist::iterator, std::greater<int> > m_map;
stage(mlist& m)
{
msrc = &m;
}
mlist::iterator operator[](int n)
{
if (n == 0)
return mlist::iterator();
map<int, mlist::iterator, std::greater<int> >::iterator itr = m_map.find(n);

if (itr != m_map.end())
{
return itr->second;
}
else
return operator[](n/2);
}
};

mlist::iterator find_mid_2(mlist ptr) {
stage probe_ptr(ptr);
auto& m_map = probe_ptr.m_map;
auto itr = ptr.begin();
m_map[1] = itr;
int len = 1;
while (itr!=ptr.end())
{
auto m_itr = m_map.begin();
int top_key=m_itr->first;
while (m_itr!=m_map.end())
{
if(m_itr->first<top_key/2)
break;
if(len==2*top_key)
m_map[len]=itr;
m_itr++;
}

itr++; len++;
}
for (auto effect:m_map)
{
int k = effect.first;
if (m_map.find(k) != m_map.end())
{
k = k / 2;
auto mid = m_map[k];
while (k++<len/2)
{
mid++;
}
cout << "res:" << *mid << endl;
return mid;
}
}
}
int main()
{
int c = 1 * 10;
mlist start;
while (c--)
{
start.push_back(c);
}
LARGE_INTEGER startCount;
LARGE_INTEGER endCount;
LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);

cal_time(find_mid_2, start);
return 0;
}

#

在我所知道的语言中,都提供了函数,但在不同语言中函数的含义也有所区别。并且一般都只提供一种含义。在erlang中函数是确定的,一旦输入确定了其对应的输出也是唯一确定的。而在C等过程式、面向对象的编程语言中,函数是代表一个过程,是若干语句的集合。那么为何不干脆把他们分开,分别实现呢?

  1. 函数(function)
    函数的输入值一旦确定了,其输出值也就确定了,不在乎过程,只关心输入与输出。因此函数具有不可变性。得益于不可变性,函数可以利用缓存技术加快处理速度。一个函数的作用域应当只存在于函数内部,函数不可对函数的外部发生修改(不能调用任务或是方法,也不能使用可变的外部变量)。因此函数的优势在于用于产生数据

不可变

缓存

无副作用

  1. 任务(task)
    任务定义了一系列语句的调用顺序。任务包含条件执行体。条件就是完成任务所需的一个或多个输入数据。执行体就是任务的功能实现。任务是异步的,只关心任务的输入,而不在乎什么时候执行。任务之间是顺序无关,只要任务的条件满足,任务就会执行。在多线程编程中应该会有大作用。
  2. 方法(method)
    这个比较传统了。方法不在乎输入或者输出,方法关心的是语句执行的过程。方法确保每条语句的正确执行。