Algorithm
Question-Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection.
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);
}
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});
}
}
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;
}
ELF 的第一种类型：.o，可重定位文件（Relocatable File）
gcc -c -fPIC process.c
gcc -c -fPIC createprocess.c
生成process.o和createprocess.o。
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。
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
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).
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
评论