ARTS 打卡 -06

用户头像
Geek_yansheng25
关注
发布于: 2020 年 07 月 12 日
ARTS打卡-06

Algorithm

Question-Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

  • Each element in the result should appear as many times as it shows in both arrays.

  • The result can be in any order.

Solution 1-std::unordered_map

class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) {
return intersect(nums2, nums1);
}
//Build a map on the shorter array
std::unordered_map<int, int> map;
for (int i = 0; i < nums1.size(); i++) {
int key = nums1[i];
auto element = map.find(key);
if (element != map.end()) {
element->second++;
}
else {
map.insert({key, 1});
}
}
//Loop through the longer array to get the result
vector<int> result;
for (int j = 0; j < nums2.size(); j++) {
int key = nums2[j];
auto element = map.find(key);
if (element != map.end()) {
if (element->second > 0) {
result.push_back(key);
element->second--;
}
}
}
return result;
}
};

Runtime beats 67.46%, while memory usage beats 49.32%.

Time complexity is O(N1+N2), while the space complexity is O(min(N1, N2)).

Solution 2-std::sort()

class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
std::sort(nums1.begin(), nums1.end());
std::sort(nums2.begin(), nums2.end());
vector<int> result;
int i = 0;
int j = 0;
while(i < nums1.size() && j < nums2.size()) {
if (nums1[i] == nums2[j]) {
result.push_back(nums1[i]);
i++;
j++;
}
else if (nums1[i] < nums2[j]) {
i++;
}
else {
j++;
}
}
return result;
}
};

Runtime beats 30.60%, while memory usage beats 66.24%.

Time complexity is O(NlogN) which comes from the sorting algorithm, while the space complexity is O(1).

Review

numpy.i: a SWIG Interface File for NumPy

https://numpy.org/devdocs/reference/swig.interface-file.html

Tips

转自极客时间课程,刘超《趣谈Linux操作系统》。

《10 | 进程:公司接这么多项目,如何管?》

1. 代码编译-ELF的三种格式

在 Linux 下面,二进制的程序也要有严格的格式,这个格式我们称为 ELF(Executeable and Linkable Format,可执行与可链接格式)。这个格式可以根据编译的结果不同,分为不同的格式。

如何从文本文件编译成二进制格式:

process.c defines a function named create_process.

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
extern int create_process (char* program, char** arg_list);
int create_process (char* program, char** arg_list)
{
pid_t child_pid;
child_pid = fork ();
if (child_pid != 0)
return child_pid;
else {
execvp (program, arg_list);
abort ();
}
}

create_process.c defines the main function that calls create_process() which is defined in process.c.

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
extern int create_process (char* program, char** arg_list);
int main ()
{
char* arg_list[] = {
"ls",
"-l",
"/etc/yum.repos.d/",
NULL
};
create_process ("ls", arg_list);
return 0;
}
  1. ELF 的第一种类型:.o,可重定位文件(Relocatable File)

gcc -c -fPIC process.c

gcc -c -fPIC createprocess.c

生成process.o和createprocess.o。

  1. ELF的第二种类型:可执行文件

ar cr libstaticprocess.a process.o

gcc -o staticcreateprocess createprocess.o -L. -lstaticprocess

在这个命令里,-L 表示在当前目录下找.a 文件,-lstaticprocess 会自动补全文件名,比如加前缀 lib,后缀.a,变成 libstaticprocess.a,找到这个.a 文件后,将里面的 process.o 取出来,和 createprocess.o 做一个链接,形成二进制执行文件 staticcreateprocess。

  1. ELF的第三种类型:共享对象文件(Shared Object)(动态链接库(Shared Libraries))

动态链接库(Shared Libraries),不仅仅是一组对象文件的简单归档,而是多个对象文件的重新组合,可被多个程序共享。

gcc -shared -fPIC -o libdynamicprocess.so process.o

gcc -o dynamiccreateprocess createprocess.o -L. -ldynamicprocess

当运行这个程序的时候,首先寻找动态链接库,然后加载它。默认情况下,系统在 /lib 和 /usr/lib 文件夹下寻找动态链接库。如果找不到就会报错,我们可以设定 LD_LIBRARY_PATH 环境变量,程序运行时会在此环境变量指定的文件夹下寻找动态链接库。

2. 运行程序,使其成为进程

知道了 ELF 这个格式,这个时候它还是个程序,那怎么把这个文件加载到内存里面呢?

我们首先通过图右边的文件编译过程,生成 so 文件和可执行文件,放在硬盘上。下图左边的用户态的进程 A 执行 fork,创建进程 B,在进程 B 的处理逻辑中,执行 exec 系列系统调用。这个系统调用会通过 load_elf_binary 方法,将刚才生成的可执行文件,加载到进程 B 的内存中执行。

Share

How to pass python numpy array to and from c++ function - using numpy.i

  1. SWIG file: postprocess.i

%module postprocess
%{
#define SWIG_FILE_WITH_INIT
#include "postprocess.hpp"
%}

%include "numpy.i"
%init %{
import_array();
%}

%apply (float* IN_ARRAY1, int DIM1) {(float* heatMapsData, int heatMapsLen), (float* pafsData, int pafsLen)};
%apply (int DIM1, float* ARGOUT_ARRAY1) {(int humanPosesLen, float* humanPoses)};

int get_num_humans();
int get_num_points_per_human();
void get_human_poses(int humanPosesLen, float* humanPoses);
void postprocess(
float* heatMapsData, int heatMapsLen,
float* pafsData, int pafsLen,
int featureMapWidth, int featureMapHeight,
int oriImgWidth, int oriImgHeight
);

SWIG uses a mechanism called typemaps to map (float* heatMapsData, int heatMapsLen), (float* pafsData, int pafsLen) to (float* IN_ARRAY1, int DIM1), and map (int humanPosesLen, float* humanPoses) to (int DIM1, float* ARGOUT_ARRAY1).



  1. Python code

def post(inf, outputMap):
frameNo = outputMap['FrameNo']
pafs = None
heatMaps = None
for key, values in outputMap.items():
if key == "Mconv7_stage2_L1":
pafs = np.frombuffer(values[0], dtype='f4')
if key == "Mconv7_stage2_L2":
heatMaps = np.frombuffer(values[0], dtype='f4')
featureMapWidth = int(inf.scale_width / 8)
featureMapHeight = int(inf.scale_height / 8)
postprocess.postprocess(heatMaps, pafs, featureMapWidth, featureMapHeight, inf.origin_width, inf.origin_height)
humanNum = postprocess.get_num_humans()
keyPointNum = postprocess.get_num_points_per_human()
humanPosesLen = humanNum * keyPointNum * 2
humanPoses = postprocess.get_human_poses(humanPosesLen)
return



用户头像

Geek_yansheng25

关注

还未添加个人签名 2020.05.21 加入

还未添加个人简介

评论

发布
暂无评论
ARTS打卡-06