2024年8月

keycloak将第三方登录(社区登录)进行了封装,大体主要会经历以下三个过程:

  1. 打开社区认证页面,输入账号密码或者扫码,完成社区上的认证
  2. 由社区进行302重定向,回到keycloak页面
  3. keycloak与社区完成一次oauth2授权码认证,通过社区返回的code来获取token,再通过token来获取社区上的用户信息,在这个过程中,社区不需要向keycloak公开用户的密码,这也是oauth2的安全性的表现
  4. keycloak检查用户是否与自己本地用户绑定,如果未绑定,进入
    第一认证流
    进行
    注册
    或者
    绑定现在有用户
    ,完成与社区的对应关系,在这个过程中,keycloak对发出
    FEDERATED_IDENTITY_LINK
    事件
  5. 用户完成绑定之后,进行
    后一认证流
    ,完成登录之后再做的事,如果用户已经完成绑定,那么
    第一认证流
    就不会进入了

回调地址的扩展

  • 当社区认证成功后,会跳转到keycloak的社区认证流
  • 当keycloak社区认证流完成后,会走到标准认证流
  • 标准认证流完成后,会重写向到来源页,并带上keycloak的code码
  • 这时,来源页上有且只有code码这个参数,如果希望扩展url上的参数,我们需要以下步骤

在社区回调地址上添加loginType参数

  • org.keycloak.services.resources.IdentityBrokerService.finishBrokerAuthentication()方法添加对loginType的操作
private Response finishBrokerAuthentication(BrokeredIdentityContext context, UserModel federatedUser,
                                              AuthenticationSessionModel authSession, String providerId) {
    authSession.setAuthNote(AuthenticationProcessor.BROKER_SESSION_ID, context.getBrokerSessionId());
    authSession.setAuthNote(AuthenticationProcessor.BROKER_USER_ID, context.getBrokerUserId());

    this.event.user(federatedUser);

    context.getIdp().authenticationFinished(authSession, context);
    authSession.setUserSessionNote("loginType", providerId);
    ...
}
  • org.keycloak.protocol.oidc.OIDCLoginProtocol.authenticated()方法中,获取loginType,并添加到回调路径的URL参数中
  code = OAuth2CodeParser.persistCode(session, clientSession, codeData);
  redirectUri.addParam(OAuth2Constants.CODE, code);
  // TODO: 登录成功后,将用户登录方式追加到回调页面上
  if (authSession.getUserSessionNotes().containsKey("loginType")) {
    String loginType = authSession.getUserSessionNotes().get("loginType");
    redirectUri.addParam("loginType", loginType);
  }

FEDERATED_IDENTITY_LINK的完善

  • 默认的绑定消息,内容比较少,不满足我们的需求
{
  "time": 1723099954167,
  "type": "FEDERATED_IDENTITY_LINK",
  "realmId": "fabao",
  "clientId": "pkulaw",
  "userId": "e62a4ea6-c1c3-4f10-9136-8ceebba45339",
  "sessionId": null,
  "ipAddress": "111.198.143.194",
  "error": null,
  "details": {
    "identity_provider": "carsi",
    "identity_provider_identity": "student@pku.edu.cn",
    "code_id": "6668189e-4cd6-488e-8582-d28b87636b41",
    "username": "phone202408081431274571"
  }
}

扩展消息,需要按以下步骤操作

  • 在org.keycloak.services.resources.IdentityBrokerService.afterFirstBrokerLogin方法中添加以下代码
  // 社区绑定现在有用户后,发的事件FEDERATED_IDENTITY_LINK,我们需要添加一些扩展信息
  event.detail(Details.IDENTITY_PROVIDER, providerId);
  event.detail(Details.IDENTITY_PROVIDER_USERNAME, context.getBrokerUserId()); //event.detail(Details.IDENTITY_PROVIDER_USERNAME, context.getUsername());
  event.detail("identity_provider_username", context.getUsername());
  • 添加之后,我们为FEDERATED_IDENTITY_LINK事件消息添加identity_provider_username
{
  "time": 1723101725866,
  "type": "FEDERATED_IDENTITY_LINK",
  "realmId": "fabao",
  "clientId": "pkulaw",
  "userId": "347c9e9e-076c-45e3-be74-c482fffcc6e5",
  "sessionId": null,
  "ipAddress": "10.10.80.81",
  "error": null,
  "details": {
    "identity_provider": "carsi",
    "identity_provider_username": "student@pku.edu.cn",
    "identity_provider_identity": "6zETJRPrWiBi7B85cCHPoVD7dyI\u003d",
    "code_id": "c344f279-9786-468b-a67e-fecf39c531b0",
    "username": "test"
  }
}

@


前言

请各大网友尊重本人原创知识分享,谨记本人博客: 南国以南i


提示:以下是本篇文章正文内容,下面案例可供参考

简介

二分查找
(Binary Search)
是一种在
有序数组中查找某一特定元素
的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到元素。

二分查找算法的效率很高,时间复杂度为O(log n),其中n是数组中的元素数量。这是因为每次比较后,搜索范围都会减半。

一、二分查找算法的原理是什么?

二分查找算法(Binary Search Algorithm)的原理基于分治法的思想,用于在有序数组中快速查找某一特定元素的位置。其核心原理可以概括为以下几个步骤:

1. 确定搜索范围:

首先,确定搜索的起始位置
low
和结束位置
high
,这两个位置分别指向数组的第一个元素和最后一个元素。这样,就确定了整个搜索范围。

2. 计算中间位置:

在每次迭代中,计算搜索范围的中间位置
mid
,这通常是通过将
low

high
相加后除以2来实现的(注意防止整数溢出,更安全的写法是
mid
=
low
+ (
high
-
low
) /
2
)。

3. 比较中间元素:

将中间位置上的元素与要查找的目标值
target
进行比较。

4. 调整搜索范围:

  • 如果中间元素正好是要查找的目标值,则查找成功,返回中间位置的索引。
  • 如果中间元素大于目标值,则说明目标值位于当前搜索范围的左半部分,因此将high更新为
    mid - 1
    ,以缩小搜索范围到左半部分。
  • 如果中间元素小于目标值,则说明目标值位于当前搜索范围的右半部分,因此将low更新为
    mid + 1
    ,以缩小搜索范围到右半部分。

5. 重复迭代:

重复步骤2至步骤4
,直到找到目标值或搜索范围为空(即
low
>
high
)。如果搜索范围为空,则说明数组中不存在目标值,此时可以返回-1或其他表示未找到的值。

二分查找算法之所以高效,是因为它每次迭代都将搜索范围减半
,从而显著减少了需要比较的元素数量。在最坏的情况下(即目标值不存在于数组中),二分查找算法的时间复杂度为O(log n),其中n是数组中的元素数量。这使得二分查找成为处理大数据集时非常有用的工具。

需要注意的是,二分查找算法要求数组必须是有序的。如果数组无序,则需要先对其进行排序,但这可能会增加总体的时间复杂度。因此,二分查找通常用于已经排序的数组或可以在查找之前进行排序的场景中。

二、二分查找算法的优缺点是什么?

二分查找算法(Binary Search Algorithm)作为一种在有序数组中查找特定元素的算法,具有其独特的优缺点。以下是二分查找算法的主要优缺点:

优点:

  1. 效率高:
    二分查找算法的时间复杂度为O(logn),其中n是数组中的元素数量。这意味着,随着数组大小的增加,查找所需的时间增长非常缓慢,相对于线性查找(时间复杂度为O(n))来说,
    效率显著提高
  2. 适用范围广:
    只要数据已经排序,就可以使用二分查找算法。这在处理大量数据且需要频繁查找的场景中特别有用,如数据库索引、文件系统中的查找等。
  3. 稳定性好:
    二分查找算法的性能不会受到数组初始排列顺序(只要是有序的)的影响,每次查找的时间复杂度都是O(log n)。

缺点:

  1. 要求数据有序:
    二分查找算法要求数据必须是有序的。
    如果数据未排序,则需要先进行排序操作,这可能会增加额外的计算开销
    。在某些情况下,如果排序成本很高,使用二分查找可能并不划算。

  2. 只适用于静态数据集或可快速更新的数据集:
    二分查找算法在查找过程中不修改原数组,因此它特别
    适用于静态数据集
    或可以快速更新的数据集。如果数据集频繁变化(如频繁插入或删除元素),则每次变化后都可能需要重新排序或调整索引,这可能会降低二分查找的效率。

  3. 需要额外空间(在某些情况下):
    虽然二分查找算法本身不需要额外的存储空间来保存中间结果(因为它直接在原数组上进行查找),但在某些应用场景下(如需要记录查找路径或进行多次查找时),可能需要额外的数据结构来辅助查找过程。

  4. 对内存敏感:
    由于二分查找依赖于数组的随机访问特性,因此在内存访问速度较慢的环境中(如使用磁盘作为存储介质时),二分查找的效率可能会受到影响。

综上所述,二分查找算法是一种非常高效的查找算法,但它要求数据必须是有序的,并且可能不适用于频繁变化的数据集。在实际应用中,需要根据具体场景和需求来选择是否使用二分查找算法。

三、java 实现二分查找案例

在Java中实现二分查找算法是一个常见的编程任务。以下是一个简单的二分查找算法实现案例,该算法用于在一个有序数组中查找一个特定的元素,并返回其索引。如果未找到该元素,则返回-1。

二叉树

public class BinarySearch {  
  
    /**  
     * 二分查找算法  
     *  
     * @param arr    有序数组  
     * @param target 要查找的目标值  
     * @return 目标值在数组中的索引,如果未找到则返回-1  
     */  
    public static int binarySearch(int[] arr, int target) {  
        int low = 0; // 定义最低点  
        int high = arr.length - 1; // 定义最高点  
  
        while (low <= high) {  
            int mid = low + (high - low) / 2; // 防止溢出,计算中间位置  
            if (arr[mid] == target) {  
                // 找到目标值,返回索引  
                return mid;  
            } else if (arr[mid] < target) {  
                // 目标值在中间位置的右侧,调整最低点  
                low = mid + 1;  
            } else {  
                // 目标值在中间位置的左侧,调整最高点  
                high = mid - 1;  
            }  
        }  
  
        // 未找到目标值,返回-1  
        return -1;  
    }  
  
    public static void main(String[] args) {  
        int[] arr = {-1, 0, 3, 5, 9, 12}; // 示例数组  
        int target = 9; // 要查找的目标值  
  
        int result = binarySearch(arr, target);  
  
        if (result != -1) {  
            System.out.println("元素 " + target + " 在数组中的索引为: " + result);  
        } else {  
            System.out.println("数组中未找到元素 " + target);  
        }  
    }  
}

在这个例子中,binarySearch 方法实现了二分查找算法。它接受一个有序数组 arr 和一个目标值 target 作为参数,并返回目标值在数组中的索引。如果未找到目标值,则返回-1。

在 main 方法中,我们创建了一个示例数组 arr 和一个要查找的目标值 target,然后调用 binarySearch 方法并打印结果。

总结

二分查找算法要求数组是有序的
。如果数组未排序,则需要先对其进行排序,然后再使用二分查找算法。此外,二分查找算法的时间复杂度为O(log n),其中n是数组中的元素数量,这使得它在处理大数据集时非常高效。**


我是
南国以南i
记录点滴每天成长一点点,学习是永无止境的!转载请附原文链接!!!

我们是
袋鼠云数栈 UED 团队
,致力于打造优秀的一站式数据中台产品。我们始终保持工匠精神,探索前端道路,为社区积累并传播经验价值。

本文作者:佳岚

可编辑表格在数栈产品中是一种比较常见的表单数据交互方式,一般都支持动态的新增、删除、排序等基础功能。

交互分类

可编辑表格一般为两种交互形式:

  1. 实时保存的表格,即所有单元格都可以直接进行编辑。
    image.png
  2. 可编辑行表格,即需要手动点击编辑才能进入行编辑状态。
    image.png

对比两种交互形式:

  1. 第一种交互更加友好,但对应的性能开销会非常大,不需要手动进入单元格编辑状态。
  2. 对于第二种交互方式,更多的场景是在数据量很大,不需要频繁修改,或者批量更新会对后端数据库操作会有较大性能影响的场景下。它还有一个很好的好处就是在
    编辑
    状态时,能够对已填入数据进行回退。

数栈产品中绝大多数都采用了第一种交互方式。
要实现一个可编辑表格,Table 组件肯定是不可或缺,是否要引入 Form 做数据收集,还要具体场景具体分析。
如果不引入 Form , 采用自行管理数据收集的方式, 其一般实现如下。

const EditableTable = () => {
  const [dataSource, setDataSource] = useState([]);

  const handleAdd = () => {
    const newData = {
      key: shortid(),
      name: 'New User',
    };
    setDataSource([...dataSource, newData]);
  };

  const handleDelete = (key) => {
    const newData = dataSource.filter(item => item.key !== key);
    setDataSource(newData);
  };

  const handleChange = (value, key, field) => {
    const newData = dataSource.map(item => {
      if (item.key === key) {
        return { ...item, [field]: value };
      }
      return item;
    });
    setDataSource(newData);
  };

  const handleMove = (key, direction) => {
    const index = dataSource.findIndex(item => item.key === key);
    const newData = [...dataSource];
    const [item] = newData.splice(index, 1);
    newData.splice(direction === 'up' ? index - 1 : index + 1, 0, item);
    setDataSource(newData);
  };

  const columns = [
    {
      title: 'Name',
      dataIndex: 'name',
      render: (text, record) => (
        <Input
          value={text}
          onChange={e => handleChange(e.target.value, record.key, 'name')}
        />
      ),
    },
    {
      title: 'Action',
      dataIndex: 'action',
      render: (_, record) => (
        <span>
          <Button
            onClick={() => handleMove(record.key, 'up')}
          >
            上移
          </Button>
          <Button
            onClick={() => handleMove(record.key, 'down')}
          >
           下移
          </Button>
          <Button onClick={() => handleDelete(record.key)}>
              删除
           </Button>
        </span>
      ),
    },
  ];

  return (
    <div>
      <Button
        onClick={handleAdd}
      >
        添加
      </Button>
      <Table
        columns={columns}
        dataSource={dataSource}
        pagination={false}
      />
    </div>
  );
};

export default EditableTable;

存在的问题:

  1. 无法对每行进行单独校验。
  2. 组件完全受控,表单数量很多时输入会卡顿严重。

优点:

  1. 非常灵活。
  2. 不用考虑
    Form
    的依赖渲染问题。
  3. 可进行表格前端分页,这能一定程度上解决性能问题。

如果使用
Form
,最正确的做法是通过
Form.List
来实现。 Form 在绑定字段时,
namePath
如果是字符串数组
["user", "name"]
,则会收集为对象结构
user.name
,如果
namePath
包含整型,则收集为数组
["users", 0, "name"]

users[0].name

Form.List
中会暴露出维护的
fields
元数据与增删移动操作的
opeartion
, 那么与
table
相结合,实现起来会变得更加简单。
其中
field
对象包含
key

name

key
是单调递增无重复的,如果删除了该数据,则
name
为其在数组中的下标。
我们为
FormItem
注册的
name
虽然是
[0, "name"]
,但是处于
Form.List
中的
Form.Item
组件都会自动拼上
parentNamePrefix
前缀,也就是最终会变成
[”users”, 0, “name”]

<Form form={form}>
    <Form.List name="users">
        {(fields, operation) => (
            <>
                <Table
                    key="key"
                    dataSource={fields}
                    columns={[
                        {
                            title: "姓名",
                            key: "name",
                            render: (_, field) => (
                                <FormItem name={[field.name, "name"]}>
                                    <Input />
                                </FormItem>
                            ),
                        },
                        {
                            title: "操作",
                            key: "actions",
                            render: (_, field) => (
                                <Button
                                    onClick={() =>
                                        operation.remove(field.name)
                                    }
                                >
                                    删除
                                </Button>
                            ),
                        },
                    ]}
                    pagination={{ pageSize: 3 }}
                />
                <Button onClick={() => operation.add({ name: "Jack" })}>
                    添加
                </Button>
            </>
        )}
    </Form.List>
</Form>

image.png
我们可以看到,使用 Form.List 实现,甚至可以使用分页,我们通过
form.getFieldsValue()
查看,数据是正常的。
image.png
为何被销毁的第一页的表单数据能够保存下来?
默认情况下
preserve

true
的字段在销毁时仍能保存数据,只是需要通过
getFieldsValue(true)
才能拿到,但对于
Form.List
, 不需要加
true
参数也能拿到所有数据。
Form.List
本身内部也是一个
Form.Item
,不过添加了
isList
来区分,不光是 List 中的子项,其本身也会被注册。如下图所示,表格中有 5 条数据,由于分页原因只有当前页的数据表单会在 Form 中注册收集,
额外的会将
users
也单独作为一个字段进行收集。
image.png
然后,在
getFieldsValue
源码中,直接就取了 Form.List 注册的值。
image.png
因此,使用
Form.List
完成分页,从源码层面分析下来是可行的,但实际没怎么见到有人这样配合用过。

应用

案例 1

以运行参数为例,其实现使用了
Table
的自定义
components
, 在
EditableCell
中再去定义表单如何渲染。
image.png

const RunParamsEditTable = () => {
    const [dataSource, setDataSource] = useState([])
    const components = {
        body: {
            row: EditableFormRow,
            cell: EditableCell,
        },
    };

    const initColumns = () => {
        return [
           // xxx字段
        ];
    };

    const columns = initColumns().map((col) => {
        if (!col.editable) {
            return col;
        }
        return {
            ...col,
            onCell: (record, index) => ({
                index,
                record,
                editable: col.editable,
                dataIndex: col.dataIndex,
                title: record[col.dataIndex] || col.title,
                errorTitle: col.title,
                save,
                // 还有很多其他状态需要传递
            }),
        };
    });
    return (
        <div>
            <Table components={components} dataSource={dataSource} columns={columns} />
            <span onClick={this.handleAdd}>添加运行参数</span>
        </div>
    );
};


EditableCell
中, 通常需要传递大量的 props 来和父组件进行通讯,且表格列定义与表单定义拆分成两个组件,这样写个人感觉太割裂了,且对于产品中绝大部分
EditableTable
来说使用自定义
components
有点大题小用。

const EditableCell = ({ editable, dataIndex, children, save, ...restProps }) => {
    const renderCell = () => {
        switch (dataIndex) {
            case 'name':
                return (
                    <Form.Item name={dataIndex} onChange={(v) => save(v)}>
                        <Input />
                    </Form.Item>
                );
            // 所有其他字段
        }
    };
    return <td>{editable ? renderCell() : children}</td>;
};

在代码中,实际又自定义了
Row
来为每一行创建一个
Form
,这样才实现的同时编辑多个行, 且 Form 只是用来做校验的,后面都通过
save
来手动收集的。假如改为上述
Form.List
的形式,那么这将会变得很好维护,在 onValuesChange 中将列表数据同步到上层
store
中。
个人认为
Table
的自定义
components
应在表格行或单元格要维护一些自身状态时才应该去考虑,如行列拖拽,单元格可在编辑状态进行切换等场景下使用。

案例 2

每个表单项都是下拉框,且下拉选项是通过级联请求过来的。
image.png
在这里,我们可能会这样做,维护一个 state 用来存放不用数据库对应的数据表列表, 并以
dbId
为键。

const [tableOptionsMap, setTableOptionsMap] = useState(new Map())


columns render
中直接消费对应的 tableOptions 进行渲染。

<FormItem dependencies={[["list", field.name, "dbId"]]}>
    {() => {
        const dbId = form.getFieldValue(["list", field.name, "dbId"]);
        const tableOptions = tableOptionsMap.get(dbId);
        return (
            <FormItem name={[field.name, "table"]}>
                <Select options={tableOptions} />
            </FormItem>
        );
    }}
</FormItem>;

这一切正常,但当我把数据加到百行数量级的时候,卡顿已经非常明显了
iShot_2024-06-22_16.26.16.gif
由于我们是把
state
存放在父组件的,每次请求会造成
table
进行 render 一遍,如果再加入 loading 等状态,render 次数会更多。
Table
组件默认情况下没有对 rerender 行为做优化,父组件更新,如果
columns
中的提供了自定义 render 方法, 对应的每个
Cell
都会重新 render 。
image.png
针对这种情况我们就需要进行优化,根据
shouldCellUpdate
来自定义渲染时机。
那么每个 Cell 的渲染时机应该是:

  1. FormItem
    增删位置变动时

  2. Cell
    消费的对应
    tableOptions
    变动时

第一种情况很好判断,
Form.List

field.name
指代下标,只需比较即可

 shouldCellUpdate: (prev, curr) => {
    return prev.name !== curr.name;
}

第二种情况我们没法直接知道
tableOptions
是否有变化,所以需要自行写个 hooks
usePreviousStateRef
,这里需要非常注意的点:返回的是
ref
而不是
ref.current
,在
shouldCellUpdate
中使用会有闭包问题。

const usePreviousStateRef = <T>(state: T): React.MutableRefObject<T> => {
    const ref = React.useRef<typeof state>();

    useEffect(() => {
        ref.current = state;
    }, [state]);

    return ref;
};

const prevTableOptionsMapRef = usePreviousStateRef(tableOptionsMap);

那么组合起来,重新渲染的条件就变成了

shouldCellUpdate: (prev, curr) => {
  // 位置变化直接渲染
  if (prev.name !== curr.name) return true;

  // 只对数据表下拉数据变动的行进行重新渲染
  const dbId = form.getFieldValue(['list', curr.name, 'dbName']),
  const prevTableInfo = prevTableOptionsMapRef.current?.get(dbId);
  const currTableInfo = tableOptionsMap?.get(dbId);

  return prevTableInfo !== currTableInfo;
},

改完后明细流畅许多
iShot_2024-06-22_17.00.38.gif
通过
shouldCellUpdate
可解决性能问题,但对应的如果 render 中依赖了外部 state, 就要自行保存 prevState 去判断了。

总结:

Form.List + Table 的组合能满足绝大部分需求,所以后续开发中最先应该考虑这种方式,当每行中存在各自状态需要维护时再尝试采用自定义 components ,永远不要 state 与 Form 混用!
此外还需要考虑足够的性能因素,特别是面对存在大量下拉框时。

最后

欢迎关注【袋鼠云数栈UED团队】~
袋鼠云数栈 UED 团队持续为广大开发者分享技术成果,相继参与开源了欢迎 star

分块

一种优化暴力的思想。

通常是将原数据划分成适当块(一般为
\(\sqrt{n}\)
),对每块数据进行预处理,进而达到比暴力更优的时间复杂度。

划分

确定块长后,一般需要开两个数组存储每一块的右边界与原数据所属块序号,更加方便后续操作。

int sq=sqrt(n);
for(int i=1;i<=sq;i++) ed[i]=n/sq*i;
ed[sq]=n;// 将剩下的都放到最后一个块内
for(int i=1;i<=n;i++)
	for(int j=ed[i-1]+1;j<=ed[i];j++)
		bl[j]=i;

区间查询

查询某区间
\(\left[L,R\right]\)
内信息,主要分为两种情况:

  1. 查询的区间位于一个块内,直接暴力即可,最坏复杂度为
    \(sq\)
  2. 查询的区间跨越多个块,分为三部分求解:
    \(\left[L,ed_{bl_{L}}\right]\)
    ,中间完整块统计,和最后
    \(\left[ed_{bl_R-1},R\right]\)
    ,最坏复杂度为
    \(\frac{n}{sq}+sq\)

在通常情况下取
\(sq=\sqrt{n}\)
时,单次查询复杂度最坏均为
\(\sqrt{n}\)

以区间求和为例,存在区间修改,提前处理每块和,代码如下:

int Query(int l,int r)
{
	int ans=0;
	if(bl[l]==bl[r])
	{
		for(int i=l;i<=r;i++) ans+=a[i]+lazy[bl[i]];
		return ans;
	}
	for(int i=l;bl[i]==bl[l];i++) ans+=a[i]+lazy[bl[i]];
	for(int i=bl[l]+1;i<bl[r];i++) ans+=sum[i];
	for(int i=r;bl[i]==bl[r];i--) ans+=a[i]+lazy[bl[i]];
	return ans;
}

区间修改

情况同查询,分为两种:

  1. 在同一块内,直接暴力修改;
  2. 不在同一块内,对于开头结尾两不完整的块暴力修改,中间完整块用 lazy 标记。

复杂度仍然为
\(\sqrt{n}\)

代码如下:

void modify(int l,int r,int k)
{
	if(bl[l]==bl[r])
	{
		for(int i=l;i<=r;i++) a[i]+=k,sum[bl[i]]+=k;
		return;
	}
	for(int i=l;bl[i]==bl[l];i++) a[i]+=k,sum[bl[i]]+=k;
	for(int i=bl[l]+1;i<bl[r];i++) lazy[i]+=k,sum[i]+=k*sq;
	for(int i=r;bl[i]==bl[r];i--) a[i]+=k,sum[bl[i]]+=k;
}

莫队

一种离线算法,基于分块思想实现。

使用莫队的前提是,对于区间查询问题,可以以
\(\mathcal{O(1)}\)
的复杂度从已知区间
\(\left[l,r\right]\)
的答案得出
\(\left[l-1,r\right]\)

\(\left[l+1,r\right]\)

\(\left[l,r-1\right]\)

\(\left[l,r+1\right]\)
的答案,那么可以在
\(\mathcal{O(n\sqrt{n})}\)
的复杂度内求出所有询问的答案。

询问预处理

要想使得每一步操作均尽可能的有效,即不进行大幅度的冗余操作,我们需要将乱序的询问提前进行排序。

通常情况下,排序标准为以左边界所属块为第一关键字,右边界为第二关键字进行升序排序,其最优性证明见下。

在一些极特殊情况,我们还可以通过奇偶化排序等方式进一步优化复杂度,通常情况下不必须使用。

复杂度分析

image

摘自 OI-wiki。

实现

HH 的项链(这道题
\(10^6\)
的数据过根号确实很极限,这里引用只是因为更简单更贴合莫队的思想)

区间求不同种类数,询问预处理就不放了,只放重要部分:

void add(int x)
{
	cnt[a[x]]++;
	if(cnt[a[x]]==1) ans++;
}
void del(int x)
{
	cnt[a[x]]--;
	if(!cnt[a[x]]) ans--;
}
int main()
{
	/*code*/
	for(int i=1;i<=m;i++)
	{
		while(l<q[i].l) del(l++);
		while(l>q[i].l) add(--l);
		while(r>q[i].r) del(r--);
		while(r<q[i].r) add(++r);
		answer[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++) printf("%d\n",answer[i]);
	return 0;
}

回滚莫队

莫队的一种扩展形式,适用于增加或删除操作其一不好维护的情况,主要分为不增加莫队和不删除莫队。

以不删除莫队举例,典型例题是求某一段区间内出现最多次数的数的数量。

思想

首先对原序列分块,将询问排序。

记录一个变量
\(las\)
,存储上一个询问左边界所在块,若与当前不同则将
\(l\)
指针移至当前询问左边界所在块右边界后一个,
\(r\)
指针移至当前询问左边界所在块右边界,保证当前为空集。

若在同一块内则暴力求解,求解后还原。

否则先将
\(r\)
向右跳至询问右边界,
同时更新计数数组和答案

之后新建一个指针
\(l_1\)
,初始值为
\(l\)
,并记录此时答案 tmp;然后向左移动指针
\(l_1\)
至询问左边界,
同时更新计数数组和答案
,此时得到当前询问的答案,记录;最后将
\(l_1\)
指针右移回到
\(l\)
的位置,此时
只更新计数数组不更新答案
,最后给答案赋值为 tmp,一次询问操作结束。

注意,第二三步的顺序不可调换,因为在移动查询区间左边界所在块的当此操作即可能为同一块内的查询,我们需要先清空计数数组再求解答案。

实现

以典型例题为例,同样只展示关键部分代码:

void add(int x)
{
	cnt[a[x]]++;
	if(cnt[a[x]]>answer) answer=cnt[a[x]];
}
void del(int x)
{
	cnt[a[x]]--;
}
int main()
{
	/*code*/
	int l=ed[bl[q[1].l]]+1,r=ed[bl[q[1].l]],las=bl[q[1].l];
	for(int i=1;i<=m;i++)
	{
		if(las!=bl[q[i].l])
		{
			while(r>ed[bl[q[i].l]]) del(r--);
			while(r<ed[bl[q[i].l]]) add(++r);
			while(l<ed[nl[q[i].l]]+1) del(l++);
			answer=0,las=bl[q[i].l];
		}
		if(bl[q[i].l]==bl[q[i].r])
		{
			for(int j=q[i].l;j<=q[i].r;j++) cnt[a[j]]++,ans[q[i].id]=max(ans[q[i].id],cnt[a[j]]);
			for(int j=q[i].l;j<=q[i].r;j++) cnt[a[j]]--;
			continue;
		}
		while(r<q[i].r) add(++r);
		int l1=l,tmp=answer;
		while(l1>q[i].l) add(--l1);
		ans[q[i].id]=answer;
		while(l1<l) del(l1++);
		answer=tmp;
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

不同数据结构都有各自优点,也都有共通之处,我们应该学到每个思想真正优势的地方,一些较麻烦的可以通过转换方法来解决(所以没写带修莫队)。

本文代码全部线上手打,有问题请指出,感谢支持。


完结撒花~

机器学习与传统编程的一个重要区别在于机器学习比传统编程涉及了更多的数学知识。
不过,随着机器学习的飞速发展,各种框架应运而生,在数据分析等应用中使用机器学习时,使用现成的库和框架成为常态,似乎越来越不需要数学知识了。

其实,现成的库和框架只是帮助我们简化机器学习的开发任务,
如果想要对模型训练结果进行调整和优化,对训练数据进行变换和过滤的话,了解相关的基础数学必能让我们事倍功半。

机器学习的模型看似一堆天书般的符号和公式,其实本质并没有那么复杂,也许大部分人只是因为没有耐心去理解其中的数学符号而放弃。
我觉得对线性代数有最基本的了解就能看懂其中大部分的公式。

本文尽量用简单的方式介绍机器学习中两个最基本的结构(
向量

矩阵
),以及它们的基本运算规则。

1. 向量

1.1. 定义

机器学习面对的训练数据,几乎没有只有单一属性的(也就是数据只包含一个数值或者一个字符串),
而是每个数据都包含多种属性,比如气象数据(包含温度,湿度,风向等等),金融数据(开盘价,收盘价,交易量等等),销售数据(价格,库存量,卖出数量等等)。

为了表示这个多属性的数据,或者称为多维度的数据,
向量
最为合适。
向量
就是有几个数字横向或者纵向排列而成,每个数字代表一个属性。
向量
类似编程语言中的一维数组,
numpy
中也是这么保存的。

1.2. 转置

向量
可以用行或者列的形式表示,
比如:
\(\begin{bmatrix}1,2,3\end{bmatrix}\)
或者
\(\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}\)


向量用

还是

来表示,主要取决于后续进行怎样的计算,本质区别不大。
向量的
转置
操作就是用来对
行向量

列向量
进行互相转换的。
image.png

1.3. 加和减

向量
之间进行加减操作时,
向量的长度
必须一样,并且必须同为
行向量
或同为
列向量

image.png
image.png
简单来说,
向量
之间的加减法就是
对应位置的元素
之间的加减法。

1.4. 积运算

向量有两种积运算,一种是向量和数值之间的积运算,也称为
标量积

另一种是向量和向量之间的积运算,也称为
内积

标量积
运算之后,向量还是向量,向量中的每个元素分别乘以标量。
image.png

内积
运算之后,向量变成一个数值(也就是标量):
image.png
计算规则就是向量对应位置的数值相乘,最后将每个位置的计算结果相加。

1.5. 模运算

向量还有一个
模运算

模运算
是一种对向量量化的方式,它把向量转换为一个数值,
从而可以方便的比较不同向量的大小。
image.png
模运算的运算符号是两个竖线:
\(||x||\)
,运算规则相当于是先计算向量与自己的内积,然后开平方。

2. 矩阵

2.1. 定义

矩阵
可以看作是相同长度的行向量或者列向量的集合。
它类似编程语言中的
二维数组

矩阵
的结构如下,其中的数据按照
矩形阵列
的结构排列,这也是
矩阵
这个名称的由来。
image.png
这是一个
3x4
的矩阵,也就是
3行4列
的矩阵。
注意,矩阵的行列数量不一定要一样,当行列数量一样时,矩阵也被称为
方阵

和向量类似,矩阵也可以转置,矩阵的转置也是行列互换:
image.png

2.2. 加和减


向量
类似,
矩阵
的加减法也是对应位置的元素进行加减运算,
这就要求参与加减运算的两个
矩阵
必须有相同的行数量和列数量。
image.png
矩阵减法运算类似。

image.png
行或列数量不一样的矩阵是无法进行加减运算的。

2.3. 积运算

矩阵的积运算也分为
标量积

内积

标量积
的计算与向量类似,矩阵的每个元素都乘以标量。
image.png

内积
运算略微复杂一些,对参与运算的矩阵也有要求,需要第一个矩阵的
列数量
等于第二个矩阵的
行数量

即:矩阵
\(A\)

\(B\)
能够进行内积运算的话,
\(A\)

\(B\)
分别为
\(M\times N\)

\(N\times K\)
的矩阵,
它们的内积是一个
\(M\times K\)
矩阵。比如:
image.png

2.4. 单位矩阵和逆矩阵

矩阵中有一种极其重要的特殊矩阵,被称为
单位矩阵

单位矩阵首先是一个方阵,并且除了对角线上的元素为
1
之外,其他元素都是
0
。比如:
image.png
单位矩阵
虽然简单,作用却不小,在矩阵分解和做高斯消元等运算时有重要的作用。

如果对于矩阵
\(A\)
,存在一个矩阵
\(B\)
,使得
\(AB=I\)
,其中
\(I\)
是单位矩阵。
那么,
\(B\)
就是
\(A\)

逆矩阵
,同时
\(A\)
也是
\(B\)

逆矩阵

\(B\)
一般表示为
\(A^{-1}\)

也就是:
\(AA^{-1}=A^{-1}A=I\)

3. 总结

向量

矩阵
是机器学习中使用最多的两种结构,比如:

  • 线性回归模型:
    \(f(x) = w_0+w_1x_1+w_2x_2+...+w_nx_n=w^Tx\)
  • 聚类函数欧氏距离:
    \(d(X_i, C_j) = ||X_i - C_j||^2\)
  • 数据正则化时的L2范数:
    \(\parallel x \parallel_2=\sqrt{\sum_{i=1}^m \mid x_{i}^2\mid}\)
  • 等等... ...

仔细观察机器学习模型中涉及的各种公式,大部分都是一些
向量

矩阵
的运算,包括加减,标量积和内积等等。
之所以觉得困难,是因为我平时生活中用的计算几乎都是标量运算,对于
向量

矩阵
的运算不熟悉,
再加上对各种数学符号不熟悉,混在一起的时候就觉得像天书一样。

其实,
向量
可以当成是一种特殊的
矩阵
,我们可以把行向量看成是
\(1\times N\)
的矩阵;
把列向量看成是
\(N\times 1\)
的矩阵。

最后,给大家留下一个小小的问题,
请问:向量和矩阵的运算有加减法和乘法的运算,却没有除法相关运算,为什么?